# Question about big O algorithm analysis

Page 1 of 1

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

### #1 kasslem2

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

# Question about big O algorithm analysis

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

• Expert Schmexpert...

Reputation: 235
• 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.

### #3 KYA

• Wubba lubba dub dub!

Reputation: 3202
• Posts: 19,233
• 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,

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12315
• Posts: 45,414
• 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.

### #5 Gloin

• Expert Schmexpert...

Reputation: 235
• 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

### #6 KYA

• Wubba lubba dub dub!

Reputation: 3202
• Posts: 19,233
• 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.

### #7 Gloin

• Expert Schmexpert...

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

## Re: Question about big O algorithm analysis

Posted 19 February 2009 - 04:56 AM

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.

### #8 KYA

• Wubba lubba dub dub!

Reputation: 3202
• Posts: 19,233
• 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.

### #9 Dr. Fox

Reputation: 2
• 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.