is unbounded for large
Chapter 12: Complexity &;! 349
So we can choose No such that ::;(n) ::; a for all n 2: No. Hence n' =
::;(n)" ::; all, proving It' = Oed').
To prove a" i= O(n') , it is enough to show that a"hl is unbounded for
large n. But we have proved that n' ::; a" for large n and any positive integer
a"
k and hence for k + 1. SO ,/+J ::; d' or t:+l:::: 1.
n
Multiplying by n, n (~) 2: n, which means a~
n k + l
n
values of 11.
I
Note: The function n 1og " lies between any polynomial function and d
1 for
any constant a. As log n 2: k for a given constant k and large values of n,
n Jog " ;:: 11' for large values of n. Hence n Jog 11 dominates any polynomial. But
10 0
Joo ,
1 .
1 1
I' (log x)2 B L"H
'1'
n ,,11= (e Jog ,,) " I =e(Jog"f.Letuscacuate 1m
. y . ospnas
x~O)
ex
. (logx)2
I'
21
lIx I'
210gx l'
2
0
rule, 11m
= 1m( ogx)- = 1m - - - = 1m - = .
x~o:
ex
x~o:
e
X~O:
ex
X~O: ex
So (log n)2 grows more slowly than en. Hence I1 Jog " = e{]og 11)2 grows more
slowly than 2'''. The same holds good when logarithm is taken over base 2
since logell and lOg211 differ by a constant factor.
Hence there exist functions lying between polynomials and exponential
functions.
12.2 THE CLASSES P AND NP
In this section we introduce the classes P and l'Ii"'P of languages.
Definition 12.5 A Turing machine M is said to be of time complexity T(n)
if the following holds: Given an input 11' of length n. M halts after making at
most T(n) moves.
Note: In this case. lH eventually halts. Recall that the standard TM is called
a deterministic TM.
Definition 12.6 A language L is in class P if there exists some polynomial
T(n) such that L = TUI1) for some deterministic TM M of time complexity
T(n).
EXAMPLE 12.2
Construct the time complexity T(n) for the Turing machine M gIven in
Example 9,7.