News for hackers. Stuff that matters.
Re:Big-O notation explained by a self-taught programmer by fmax30 on Saturday July 27, 2013 @02:44AM (#6112081)
I don't really know why Big-O notation is so common , even though Big O is the upper bound . For me it is more practical and logical to use the Big Θ (Theta) notation as it provides a tighter bounder which is more understand able. Also Big O is very misleading to the new comers, as they are usually confused when they see something like O(n) = O(n^2) which is perfectly valid , as the Big O notation is only the upper bound albeit it will be a loose upper bound.

For all we care , we can write the Big O of

for ( i = 0 ; i < n ; i++) { cout<<"I am constant time operation"; }

as O( n!) , it won't be mathematically wrong but again it would be very misleading and loose :). So my advice to everyone is to use the Big Θ notation

As f(x)= Big Θ(g(x)) when f(x) = Big O ( g(x) ) and Big Ω(g(x)) .

Here for those that don't know what Big Ω(g(x)) (read Big omega) is, it is a lower bound . In English that would be that your loop will execute/iterate at least g(x) times.

Now before people get any more confused Big Θ(g(x)) is a tight bound , that means that your code/loop will run at least C1 * (g(x)) and at most C2 * (g(x)) . where C1 and C2 are two constants .

If anyone is interested they should really read CLRS. It has an excellent chapter on calculating and explaining the time complexities.

Re:Big-O notation explained by a self-taught programmer by xentronium on Saturday July 27, 2013 @03:12AM (#6112115)
Theta is much harder to type and slightly harder to write. Besides, people are trying to be reasonable about their bounds.
Re:Big-O notation explained by a self-taught programmer by oskarkv on Saturday July 27, 2013 @03:41AM (#6112151)
Of course O(n) is not equal to O(n^2). O(n) is a set, and O(n^2) is a different set.
Re:Big-O notation explained by a self-taught programmer by fmax30 on Saturday July 27, 2013 @07:24AM (#6112538)
Big O is a upper bound , what I meant was that if a piece of code has O(n) then it also has O(n^2). With emphasis on the upper bound f(x) = O(g(x)) if f(x) <= cg(x).

so my point is if f(N) = O(N) then f(N) is also equal to O(N^2) as f(N) <= CN^2 .