[kasslem2]

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

[Gloin]

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.

[KYA]

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,

[macosxnerd101]

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.

[Gloin]

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

[KYA]

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

[Gloin]

KYA, 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.

[KYA]

My apologies, I didn't see the '*' between n^3 and log n. That would be terrible to do by hand.

[Dr. Fox]

Graphing running times for asymptotic analysis is bad advice... don't do it. Never graph a program to determine its time complexity, ever.