Saturday, 5 January 2013

Asymptotic growth of function (Comparision)

Rules for comparing asymptotic growth of functions
1)f(n) < g(n) if





2) if f(n) < g(n)  then 1/g(n) < 1/f(n)

Ordering functions according to their asymptotic growth

1) nα < nβ 
whenever β>α
Examples
n1.2 < n2
n0.02 < n0.2

2) 1 < log(log n) < log n < nε < nC < nlog n < Cn < nn < CCn
where 0 < ε < 1 and C > 1
because  f(n)/g(n) --> infinity  as n --> infinity  for each f(n) < g(n)
Examples
nlog n < 2n
log n < n0.0001
nn < 22n

3)Using the reciprocal rule in above hierarchy we can deduce that
1/nε < 1 / log n 
1/nε < 1
and so on

4) log n!  <  n log n

5)2n  <  en  <  n!  < 22n

Reference
Concrete Mathematics, Graham Knuth Pattasnik
Algorithms, Cormen   Leiserson   Rivest

No comments:

Post a Comment