Chapter 12: Complexity ,l;l, 347
Definition 12.1 Let ,j; g : N -7 R+ (R+ being the set of all positive real
numbers), We say that fen) = O(g(n» if there exist positive integers C and
No such that
f(n) S Cg(n)
for all n ~ No,
In this case we say f is of the order of g (or f is 'big oh' of g)
Note: f(n) = O(g(n» is not an equation. It expresses a relation between two
functions f and g.
EXAMPLE 12.1
Let f(n) = 4n
3 + 511
2 + 7n + 3. Prove that f(n) = 0(n
3 ).
Solution
In order to prove that f(n) = 0(n
3 ), take C = 5 and No = 10. Then
f(n) = 4n
3 + 5n
2 + 7n + 3 S 5n
3
for n ~ 10
\Vhen n = 10. 511
2 + 7n + 3 = 573 < 10
3 . For 11 > 10, 5n
2 + 7n + 3 < n
3
•
Then, f(n) = 0(11\
Theorem 12.1 If pen) = Gk1/ + Gk_lnk-I + ... + ([In + Go is a polynomial
of degree k over Z and az, > 0, then pen) = O(nk).
Proof pen) = Qk1/ + aZ_ln
k
-
1 + ... + Gin + Go. As Qk is an integer and
positive, (lk ~ 1.
As {[i-i' aZ-2' ... , (Ii' ao and k are fixed integers, choose No such that for
all 11 ~
each of the numbers
Hence,
n
lak-21
l a11 lao I
1
-~2-' .. ,,~. k is less than
n
11
n
k
(*)
Also.
for all n 2 No
So,
S az + 1
pen) S 0/.
by (*)
where
Hence.
p(ll) = O(n
k ).