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