This notation is used as a measure of
complexity.
Personally, I find the standard definition ("if there exists a constant such that for all N>n") to be annoyingly obfuscated. A much simpler way (IMO) to state it:
-
f(x) is in big-oh(g(x)), if limn->inf.( f(n)/g(n) ) is less than infinity.
-
f(x) is in small-oh(g(x)), if limn->inf.( f(n)/g(n) ) is zero.
-
f(x) is in theta(g(x)), if limn->inf.( f(n)/g(n) ) is finite but not zero
(Assuming that all f(x) and g(x) only have positive values, otherwise you have to take
absolute values)