Big O notation

[shinta]

include Detailed information on the Big O? im not so sure of what it is and how it works.

[WingedPanther]

Big O is not a language specific concept. It is an upper bound of the measurement of an algorithm's efficiency (usually either memory or time). When analyzing an algorithm, you aren't looking for whether the there are a lot of lines, but the types of loops that are present (along with implicit loops due to recursive function calls).

The formal definition (from memory) is the following:
A function g(x) is considered O(f(x)) if there exists C and X such that, for all x>X, C*f(x) > g(x).

Human translation: g(x) is bounded above by a scalar multiple of f(x) for all sufficiently large x.

This has a few implications that are relevant:
1) x^2, 2*x^2, 3*x^2, etc are all O(x^2) (where x^2 is x squared)
2) trivial cases such as x=1, x=2, x=3, are usually not relevant for analysis.
3) x^2 is O(x^2), O(x^3), O(x^4) etc. So knowing an algorithm is O(x^2) does not mean that it can't be more efficient, but rather that x^2 is a worst-case scenario that may not actually occur.

Some basic big-O's listed in order from best to worst are:
O(1), O(ln(x)), O(sqrt(x)), O(x), O(x^n), O(n^x), O(x!)

For rough and dirty analysis, code with no loops/function calls is O(1). Code with a single for loop is O(x), code with nested for loops is O(x^n) where n is the level of nesting. Code with recursive function calls can range from O(ln(x)) to O(x!) or worse.

Interesting side note. I wrote a sorting problem a while back that I believe was O(((x!)!)!). It ran nicely when the input was 9 and 3 (took about a minute), sucked when the input was 12 and 3 (didn't finish after running for 5 hours).

[G_Morgan]

You've missed O(nlog(n)) which is the theoretically the most efficient you can make a comparison sorting algorithm in the worse case.

Big O is about mathematics. A field called computational complexity. Basically, how long does an algorithm take to finish given various characteristics of the data set. Usually we consider size (how long does a sort take given a list of size n) of the data set but computational complexity also alters depending on the composition of the data set. Take insertion sort, it scales O(n^2) but it takes much longer for data that is reverse sorted than it does some average set of data. Counting sort OTOH varies with the range and size of the data set, data sets where the highest and lowest values are 1 and 1m will sort far slower than data sets of the same size but where the extreme values are 1 and 10.