Question

6- Rank the following functions by increasing order of growth. That is, find

any arrangement g1,g2,g3,g4,g5,g6,g7,g8 of the functions satisfying g1 = O(g2),

g2= O(g3), g3= O(g4), g4= O(g5), g5= O(g6), g6= O(g7), g7= O(g8). [2 points]

f1(n)= n^e   f2(n)=πⁿ   f3(n)=(n+1)!/2    f4(n)=lnlnn f5(n)=lgn   f6(n)=eⁿ    f7(n)= n^πlgn   f8(n)=eπ

Answer 1

As a general rule we have,

constant< logarithmic< (polynomial,poly-logathmic)< (exponential,factorial)

constant: e.pi

logarithmic: lnln(n),logn

poly-logarithmic: n^pi log(n)

polynomial: n^e

exponential:eⁿ ,piⁿ

factorial: (n+1)!/2

_________________________________________________

loglog(n)<log(n) since log(n)<n.

n^e<n^pilog(n) since pi>e and log(n)>1 for n>=2

Similarly eⁿ<piⁿ because e<pi

Hence e.pi<lnln(n)<log(n)<n^e<n^pilog(n).

Now we only require to fix (n+1)!/2

By stirling pproximation we know,

which means factorial grows the fastest, Hence the complete sequence is

e.pi<lnln(n)<log(n)<n^e<n^pilog(n)<eⁿ<piⁿ<(n+1)!/2