Applied Math Applied Math Forum

 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:
 Originally Posted by baxy7 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?)
It's linear in n and linear in m. Normally, this is what computer scientists mean by "linear-time".

Quote:
 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 ?
You're in the same complexity class with respect to n. Not with respect to m (The function is constant in m). The idea is, O(f) (For a f a function of some variables) is only meaningful with respect to variables in f. This becomes really important in combinatorial optimization, where you'll let a term go to zero since the function is O(1), with respect to some variable, because the rest of the variables you can assume to be fixed.

Quote:
 thank you!
Cheers! Feel free to ask for clarification. April 18th, 2009, 11:50 AM   #3
Newbie

Joined: Mar 2009

Posts: 27
Thanks: 0

Re:Re: complexity problem

Quote:
 Feel free to ask for clarification.
but if the case is :

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

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:
 Originally Posted by baxy7 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.....
To add to what you've noted and what CRG pointed out, if m=f(n), then O(mn) = O(nf(n)), which isn't necessarily linear in n.

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 "non-linear" 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:
 How is "search through file of size m" atomic!?
by my definition, i'm trying to generalize the 'problem' (example) to understand it. if i did something that i shouldn't by any cost, please tell me

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
}
}
where m is a file size, z is a file size, mi,x , zi,x -> i-th or x-th part of the file in question Tags complexity, problem ### cxnxnxnx

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post ChessTal Computer Science 7 December 25th, 2018 11:17 AM courteous Computer Science 0 August 31st, 2010 02:55 AM ulita Computer Science 2 August 18th, 2010 07:56 AM mcaos Computer Science 4 June 1st, 2010 12:57 PM UnOriginal Applied Math 2 August 26th, 2009 08:05 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top       