complexity problem quick question about defining time complexity : my problem is solvable in linear time and the calculation depends on 2 parameters n and m : O(nm) (am i right to conclude that the time to get the solution is linear if i have 2 changeable factors?) and now i have some other algorithm that does the same thing but it only depends on factor n to get the same result , so the big O is: O(n) now my question is am i still in the same complexity class or not? if not, in which class am i ? thank you! ps just started learning about Computational complexity :) update: obviously i didn't understand the linear part :oops: 
Re: complexity problem If you changed the size, I'd appreciate it if you didn't in the future. :) Quote:
Quote:
Quote:

Re:Re: complexity problem thank you for the reply Quote:
m = n x c then : O(mn) = O(n x n x m x c) => O(c x n^2 ) and if i'm free to neglect constant c then O(n) != O(n^2) then would i be in the same class? as i figure this is then not the same class, one is linear where the other is polynomial, RIGHT ???? the confusing part is that i have this example where O(mn) is polynomial and O(m+n) is linear but then later in the text it refers to O(mn) as linear. so i am looking for a logical explanation (example) when O(mn) ca be polynomial and when linear i'm writing polynomial instead of quadric because m could be : m = c x n x n x n x..... 
Re: complexity problem It's linear in n if m is constant. If m = nc then m isn't constant. 
Re: Re:Re: complexity problem Quote:
Also, f(n) is polynomial in n means f(n) = O(n^k) for some integer k. So linear ==>polynomial. (Although the authors may clarify that "nonlinear" is implied when they say polynomial) I have a sneaking suspicion that in some of these examples, n=V(G) and m=E(G) for some graph G. In this case, m=O(C(n,2)) = O(n^2) [where C(n,2) is n choose 2], so O(nm) = O(n)O(n^2) = O(n^3), which is polynomial in n. Does that help? 
Re: complexity problem thnx , for the reply, i think i'm beginning to understand now, and i have one more question for the end :D : if i have algorithm that goes something like this : for (1..n){ print x } result for n = 5: > xxxxx O() for this algorithm is O(n) right?? and if i write: print xxxxx then i achieved the same thing but what is my O() here and are thees two algorithms in the same class 
Re: complexity problem Technically, that depends on the implementation of print. :) In reality, every implementation of print actually runs in O(n) for n characters: only one character can be dealt with at a time. So the loops is n*O(1)=O(n) and print(xxxx...) = O(n) I think print is considered to be an O(n) operation by most algorithm researchers... but I don't know for sure. If print is O(1), then print(xxx...) is O(1) and the loop is O(n); Otherwise, they are in the same complexity class. This is getting at something you have to keep in mind when actually designing programs: Complexity only goes so far. In the two examples, a good optimizer will compile the loop down to the single print, but if the two snippets compiled to straight assembly without optimization, the single print should run faster than the loop (despite the complexity). Similarly, Fibonacci heaps are typically not worth the effort when actually writing a program, despite their excellent amortized performance. 
Re: complexity problem ok please help me with this one then :) 1. for (1..n){ search through file of size m /* atomic 'by definition' */ search through another file size z /* so that every iteration i'm increasing z file by size z } 2. for (1..n){ search through file of size m /* so that every time the m file is decreased by (1/n )*m search through file z } 3. search through m for (1..n){ search through z } what are the O() for these three procedures. ask for clarification if this is not understandable because i don't know which things are important to mention :oops: please help !!!!! :?: 
Re: complexity problem How is "search through file of size m" atomic!? 
Re: complexity problem Quote:
update : ok, let me extrapolate previous algorithms (because now i think i understand CRG's point :) ) Code: 1. 
All times are GMT 8. The time now is 08:28 PM. 
Copyright © 2019 My Math Forum. All rights reserved.