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
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