Click here to go to the NEW College Discussion Forum

I'm having trouble with Big O Notation, more specifically when they give you code and you are asked if something is O(n) or O(log n), etc.

How are you suppose to know what it is?

Can someone list and describe what each one is?
I think they are: O(1), O(n), O(log n), O(n log n), O(n^2). I believe I just listed them in order of decreased efficiency for large lists, right?

By Wishful_Thinker (Wishful_Thinker) on Monday, May 03, 2004 - 12:19 am: Edit

use Barron's or PR

By Zik (Zik) on Monday, May 03, 2004 - 01:39 am: Edit

O(log n) is faster than O(n)

By Techieguy (Techieguy) on Monday, May 03, 2004 - 03:23 pm: Edit

The only ones that confuse me are the O(log n) and the O(n log n) ones, how do you know that the code is this speed?

By Firebird12637 (Firebird12637) on Monday, May 03, 2004 - 05:50 pm: Edit

n log n is dependent on both the length of the array and the times its divided

log n is just the number of times it can be divided

By Collegeek (Collegeek) on Monday, May 03, 2004 - 05:53 pm: Edit

firebird: could u please elaborate on what u meant by divided ... im not understanding what u meant completely ..... thanks

By Aspirer42 (Aspirer42) on Monday, May 03, 2004 - 06:58 pm: Edit

O(log N) I've found most often this year when you're doing binary trees. For example, in a binary search tree with N nodes, it will take you approximately (log N) comparisons to find a specific value, or any leaf for that matter.

O(N log N) is used for some of the more advanced sorts--our textbook lists Mergesort and Quicksort among them. I do hope we wouldn't have to identify a program with that big O on the exam, since it would have to be rather complicated.

I think that O(x^N), where x is some generic integer, is also a recognized big O, but you'll only find that in the beastliest and most inefficient of programs, particularly in recursion.