Let's consider f(n) > 0
and g(n) > 0
for all n
. It's ok to consider this, because the fastest real algorithm has at least one operation and completes its execution after the start. This will simplify the calculus, because we can use the value (f(n)
) instead of the absolute value (|f(n)|
).
f(n) = O(g(n))
General:
f(n)
0 = lim -------- < 8
n?8 g(n)
For g(n) = n
:
f(n)
0 = lim -------- < 8
n?8 n
Examples:
Expression Value of the limit
------------------------------------------------
n = O(n) 1
1/2*n = O(n) 1/2
2*n = O(n) 2
n+log(n) = O(n) 1
n = O(n*log(n)) 0
n = O(n²) 0
n = O(nn) 0
Counterexamples:
Expression Value of the limit
-------------------------------------------------
n ? O(log(n)) 8
1/2*n ? O(sqrt(n)) 8
2*n ? O(1) 8
n+log(n) ? O(log(n)) 8
f(n) = T(g(n))
General:
f(n)
0 < lim -------- < 8
n?8 g(n)
For g(n) = n
:
f(n)
0 < lim -------- < 8
n?8 n
Examples:
Expression Value of the limit
------------------------------------------------
n = T(n) 1
1/2*n = T(n) 1/2
2*n = T(n) 2
n+log(n) = T(n) 1
Counterexamples:
Expression Value of the limit
-------------------------------------------------
n ? T(log(n)) 8
1/2*n ? T(sqrt(n)) 8
2*n ? T(1) 8
n+log(n) ? T(log(n)) 8
n ? T(n*log(n)) 0
n ? T(n²) 0
n ? T(nn) 0