April 18th, 2009, 05:07 AM  #1 
Newbie Joined: Mar 2009 Posts: 27 Thanks: 0  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 
April 18th, 2009, 09:08 AM  #2  
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: complexity problem
If you changed the size, I'd appreciate it if you didn't in the future. Quote:
Quote:
Quote:
 
April 18th, 2009, 11:50 AM  #3  
Newbie Joined: Mar 2009 Posts: 27 Thanks: 0  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.....  
April 18th, 2009, 12:07 PM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: complexity problem
It's linear in n if m is constant. If m = nc then m isn't constant.

April 18th, 2009, 02:56 PM  #5  
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  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?  
April 19th, 2009, 06:28 AM  #6 
Newbie Joined: Mar 2009 Posts: 27 Thanks: 0  Re: complexity problem
thnx , for the reply, i think i'm beginning to understand now, and i have one more question for the end : 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 
April 19th, 2009, 09:54 AM  #7 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  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. 
April 20th, 2009, 04:55 AM  #8 
Newbie Joined: Mar 2009 Posts: 27 Thanks: 0  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 please help !!!!! 
April 20th, 2009, 07:17 AM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: complexity problem
How is "search through file of size m" atomic!?

April 20th, 2009, 09:27 AM  #10  
Newbie Joined: Mar 2009 Posts: 27 Thanks: 0  Re: complexity problem Quote:
update : ok, let me extrapolate previous algorithms (because now i think i understand CRG's point ) Code: 1. for(x = 1; x < n; x++){ while(m){ ... one atomic } for (i = 1; i < x; i++){ while(zi){ ... one atomic } } } 2. for (x = 1; x < n; x++){ while(m  ((1/x)m)){ ... one atomic } while(zx){ ... one atomic } } 3. while(m){ ... one atomic } for (x = 1; x < n; x++){ while(zx){ ... one atomic } }  

Tags 
complexity, problem 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Big O complexity  courteous  Computer Science  0  August 31st, 2010 02:55 AM 
O(sin n), ?(sin n), ?(sin n) complexity  ulita  Computer Science  2  August 18th, 2010 07:56 AM 
Complexity Theory  Multiple ways to describe a problem  mcaos  Computer Science  4  June 1st, 2010 12:57 PM 
Computability/Complexity problem related to Lotto/Keno.  ChessTal  Computer Science  3  January 27th, 2010 08:23 AM 
Complexity of Problem  UnOriginal  Applied Math  2  August 26th, 2009 08:05 AM 