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*)=π* ^{n}*
f3(

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^{n} ,pi^{n}

factorial: (n+1)!/2

_________________________________________________

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

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

Similarly e^{n}<pi^{n} because e<pi

Hence
e.pi<lnln(n)<log(n)<n^{e}<n^{pi}log(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^{pi}log(n)<e^{n}<pi^{n}<(n+1)!/2

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 12 minutes ago

asked 22 minutes ago

asked 45 minutes ago

asked 48 minutes ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago