My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Applied Math (http://mymathforum.com/applied-math/)
-   -   complexity problem (http://mymathforum.com/applied-math/6566-complexity-problem.html)

baxy7 April 18th, 2009 04:07 AM

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:

cknapp April 18th, 2009 08:08 AM

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.

baxy7 April 18th, 2009 10:50 AM

Re:Re: complexity problem
 
thank you for the reply

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

i'm writing polynomial instead of quadric because m could be :
m = c x n x n x n x.....

CRGreathouse April 18th, 2009 11:07 AM

Re: complexity problem
 
It's linear in n if m is constant. If m = nc then m isn't constant.

cknapp April 18th, 2009 01:56 PM

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?

baxy7 April 19th, 2009 05:28 AM

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

cknapp April 19th, 2009 08:54 AM

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.

baxy7 April 20th, 2009 03:55 AM

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 !!!!! :?:

CRGreathouse April 20th, 2009 06:17 AM

Re: complexity problem
 
How is "search through file of size m" atomic!?

baxy7 April 20th, 2009 08:27 AM

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


All times are GMT -8. The time now is 02:25 AM.

Copyright © 2019 My Math Forum. All rights reserved.