My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
baxy7 is offline  
 
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.
cknapp is offline  
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:
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.....
baxy7 is offline  
April 18th, 2009, 12:07 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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?
cknapp is offline  
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
baxy7 is offline  
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.
cknapp is offline  
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 !!!!!
baxy7 is offline  
April 20th, 2009, 07:17 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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!?
CRGreathouse is offline  
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
baxy7 is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2018 My Math Forum. All rights reserved.