edited by
7,461 views
3 votes
3 votes
Arrange the following functions in asymptotically increasing order

f1(n) = n0.999999 log n

f2(n) = 10000000n

f3(n) = 1.000001n

f4(n) = n2

Ans is  f1, f2, f4, f3

I am not understanding how f1(n) grows asymptotically slower than f2(n)
edited by

1 Answer

3 votes
3 votes
$f1(n)=n^{0.999999}logn\\ f2(n)=1000000n\\ f3(n)=1.000001^{n}\\ f4(n)=n^{2}$

We know order of growth of$f4(n)$ an exponential function is higher than all other given function, so it is largest among all.

Since $f3(n)$ is exponential and $f4(n)$ is quadratic then $f4(n)$< $f3(n)$, as quadratic grows slower than exponential.

$f2(n)$ is linear while $f4(n)$ is quadratic so $f2(n)$<$f4(n)$

Now we have to check between $f1(n)$ and $f2(n)$,

 $f1(n)=n^{0.999999}logn,  \  f2(n)=1000000n\cong n(constant \ can \ be \ neglected)$

$f2(n)=n=n^{0.999999}n^{0.000001}$

Common part can be removed from both $f1(n) and f2(n)$

Now $f1(n)=logn$ and $f2(n)=n^{0.000001}$

It is clear that for large values of n $f1(n)$ grows slower than $f2(n)$, another way to check this is, we can substitute $n=2^{m}$ in both the function then

$f1(m)=m$ and $f2(m)=2^{0.000001m}$, hence $f1(n)<f2(n)$

Hence increasing order is $f1(n)<f2(n)<f4(n)<f3(n)$

Related questions

1 votes
1 votes
2 answers
1
Durgesh Singh asked Dec 10, 2017
2,457 views
Realtime DPDA with Null Store,Real time DPDA with final state, DPDA with NULL store,DPDA with final state, NPDA
2 votes
2 votes
2 answers
2
Sankaranarayanan P.N asked Jun 4, 2015
2,203 views
arrange the following in the increasing order of their asymptotic complexity in big theta notation$2^{2^{n}}, \log n ^{\log n} , (\frac{3}{2})^{n}, 2^{n}, \log n!$