8 Replies - 4650 Views - Last Post: 21 February 2009 - 01:13 PM

#1 kasslem2  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 31-January 09

Question about big O algorithm analysis

Post icon  Posted 31 January 2009 - 11:12 AM

Hey, I hope I put this in the right section. I have a basic question about big o notation. How do you discover if something is O(logn) vs O((logn)^2)? It seems like the graphs are similar, but (logn)^2 has a slightly faster growth rate. I don't know how you would be able to tell for sure. I plug in values for n ( the number of times for a program to run), and then graph the time it takes, and it looks like (logn)^2.

Also, I have read how to calculate big O for for loops, nested for loops, etc. but I have not seen anything for what to do if the for loop does not increment by 1 each time. What if you increase the amount to increment by for 1 each time? So first is n+1, then n+2, n+3,...etc. Graphing that is what looked like (logn)^2 to me, but I'm not sure how to tell for sure.

Sorry if that is confusing,

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Question about big O algorithm analysis

#2 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Question about big O algorithm analysis

Posted 01 February 2009 - 05:51 AM

A bit confusing but basically, you calculate big O by analysis. Most logarithmic-complexity functions use recursion so what you do is you write down the recursion equation and solve it.

You can't really solve it by looking at run-times because any function that takes c * log(n) time to perform (where c is any constant) is O(log n).
If you have the graph then possible you can derive the answer.
Was This Post Helpful? 0
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Question about big O algorithm analysis

Posted 01 February 2009 - 10:32 AM

You can also do it through calculus. If I recall correctly, you take the limit and divide and depending on the answer, the original equation is big order ("O") or little order ("o" of the equation used to check,
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10461
  • View blog
  • Posts: 38,766
  • Joined: 27-December 08

Re: Question about big O algorithm analysis

Posted 17 February 2009 - 12:25 PM

I'm a high school student in pre-AP CS, so my answer may be a little cruder than the other 2. What I do is increase the size of the problem and record the nubmer of steps for each increment. I then graphed these points and used the function which represented the curve followed. For example, if 1/2 of a parabola was formed, the function was O(n^2). Even if it wasn't an exact graph of n^2, it followed the same pattern.
Was This Post Helpful? 0
  • +
  • -

#5 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Question about big O algorithm analysis

Posted 18 February 2009 - 03:33 AM

How do you identify a complexity function that is something like 'n^3 * log n' or 'n * (log n)^2'?

This post has been edited by Gloin: 18 February 2009 - 03:34 AM

Was This Post Helpful? 0
  • +
  • -

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Question about big O algorithm analysis

Posted 18 February 2009 - 07:46 AM

A cubic function makes a distinguishing graph. Not sure on the n log n one though.
Was This Post Helpful? 0
  • +
  • -

#7 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Question about big O algorithm analysis

Posted 19 February 2009 - 04:56 AM

View PostKYA, on 18 Feb, 2009 - 02:46 PM, said:

A cubic function makes a distinguishing graph. Not sure on the n log n one though.


Sure, but the n^3 * log n as from my example is not so easily differentiated from the n^2 * log n. Like you say, as long as you're close to some distinct graph you'll probably do ok but as soon as you have to deal with some more complex function you're in for some problems.

Compare these 2 graphs in for example range [-10, 10] and you'll see that they look quite similar.
n * log(n^2)
and
0.01 * n^3

Naturally the later will outgrow the first rather quickly although that is not indicated by the graph. They look very similar and one can easily be mistaken for the other.
Was This Post Helpful? 0
  • +
  • -

#8 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Question about big O algorithm analysis

Posted 19 February 2009 - 07:27 AM

My apologies, I didn't see the '*' between n^3 and log n. That would be terrible to do by hand. :)
Was This Post Helpful? 0
  • +
  • -

#9 Dr. Fox  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 12
  • Joined: 02-March 08

Re: Question about big O algorithm analysis

Posted 21 February 2009 - 01:13 PM

Graphing running times for asymptotic analysis is bad advice... don't do it. Never graph a program to determine its time complexity, ever.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1