Question

# 6- Rank the following functions by increasing order of growth. That is, find any arrangement g1,g2,g3,g4,g5,g6,g7,g8...

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)= ne   f2(n)=πn   f3(n)=(n+1)!/2    f4(n)=lnlnn f5(n)=lgn   f6(n)=en    f7(n)= nπlgn   f8(n)=eπ

As a general rule we have,

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

constant: e.pi

logarithmic: lnln(n),logn

poly-logarithmic: npi log(n)

polynomial: ne

exponential:en ,pin

factorial: (n+1)!/2

_________________________________________________

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

ne<npilog(n) since pi>e and log(n)>1 for n>=2

Similarly en<pin because e<pi

Hence e.pi<lnln(n)<log(n)<ne<npilog(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)<ne<npilog(n)<en<pin<(n+1)!/2

#### Earn Coins

Coins can be redeemed for fabulous gifts.