Big O
Big O (uppercase Omicron, but O is close enough) is the asymptotic upper bound on a function. The formal definition is:
f(n) = BigO(g(n)) if,
for some constants c and k, 0<= f(n) <=cg(n), for all n >= k.
Basicly once you get n big enough(pass k), then cg(n) will always be greater than or equal to f(n).
For computer algorithms, often what is measured is speed or space. Space can easily be measured in bytes or bits:
An algorithm with a space requirment of O(n^2) bytes.
Speed needs to be quantified somehow. It can be by arithmatic operations, element swaps or compares, or some other method.
An algorithm with O(n * log(n)) element compares.
A little quirk, if f(n) = O(n^c), then also, f(n) = O(n^k), where k > c, beacuse the subsequent functions, O(n^k), will be greater than O(n^c). Therefore any function that is O(n^3) will also be O(n^4), O(n^3.1), O(n^234), etc.
Some of BigO's relatives are:
LittleO, written o(n) - same as BigO but strictly greater than instead of greater than or equal to
Omega - Less than or equal to. Also the asymptotic lower bound of an equation.
Theta - a function that is both an upper and lower bound. The intersection of all O(g(n)) and Omega(g(n)) for a given f(n). In form as above:
f(n) = Theta(g(n)) if,
for some constants c1, c2, and k
0 <= c1g(n) <= f(n) <= c2g(n)
And there's more than you ever wanted to know about BigO!
Karg
[edited by - Karg on March 5, 2003 12:45:25 AM]
f(n) = BigO(g(n)) if,
for some constants c and k, 0<= f(n) <=cg(n), for all n >= k.
Basicly once you get n big enough(pass k), then cg(n) will always be greater than or equal to f(n).
For computer algorithms, often what is measured is speed or space. Space can easily be measured in bytes or bits:
An algorithm with a space requirment of O(n^2) bytes.
Speed needs to be quantified somehow. It can be by arithmatic operations, element swaps or compares, or some other method.
An algorithm with O(n * log(n)) element compares.
A little quirk, if f(n) = O(n^c), then also, f(n) = O(n^k), where k > c, beacuse the subsequent functions, O(n^k), will be greater than O(n^c). Therefore any function that is O(n^3) will also be O(n^4), O(n^3.1), O(n^234), etc.
Some of BigO's relatives are:
LittleO, written o(n) - same as BigO but strictly greater than instead of greater than or equal to
Omega - Less than or equal to. Also the asymptotic lower bound of an equation.
Theta - a function that is both an upper and lower bound. The intersection of all O(g(n)) and Omega(g(n)) for a given f(n). In form as above:
f(n) = Theta(g(n)) if,
for some constants c1, c2, and k
0 <= c1g(n) <= f(n) <= c2g(n)
And there's more than you ever wanted to know about BigO!
Karg
[edited by - Karg on March 5, 2003 12:45:25 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement