edited by
4,477 views
28 votes
28 votes

Which of these functions grows fastest with $n$?

  1. $e^{n}/n$.
  2. $e^{n-0.9 \log n}$.
  3. $2^{n}$.
  4. $\left(\log n\right)^{n-1}$.
  5. None of the above.
edited by

3 Answers

Best answer
58 votes
58 votes

Assuming that the base of the $\log$ in the question is $e$.

Let us try to rewrite each of these functions in the form $e^{\,\small\rm something}$, to make the comparison easier.

$$\def\d{\displaystyle\,}
\begin{array}{l|ll}
a. & e^{n} / n & = \dfrac{e^{\d n}}{e^{\d(\ln n)}} & = e^{\d (n - \ln n)}\\[1em]
b. & e^{n - 0.9 \ln n} &&= e^{\d (n - 0.9 \ln n)}\\[1em]
c. & 2^n &= \left (e^{\d\ln 2} \right )^{\d n} &= e^{\d (n \ln 2)}\\[1em]
d. & (\ln n)^{n-1} &= \left (e^{\d\ln \ln n} \right )^{\d n-1} &= e^{\d (n \ln \ln n - \ln\ln n)}
\end{array}$$

Now, if we just compare the exponents of all, we can clearly see that $(n \ln \ln n - \ln \ln n)$ grows faster than the rest. Note that in option $(C)$, the multiplicative $\ln 2$ is a constant, and hence grows slower than the multiplicative $\ln \ln n$ from option $(D)$.

This implies that $e^{\d (n \ln \ln n - \ln\ln n)}$ grows the fastest, and hence, $(\ln n)^{n-1}$ grows the fastest.

Thus, option (D) is the correct answer.

edited by
3 votes
3 votes
a)(e^n)/n

b)e^(n-0.9logn) =(e^n)/n^0.9 meaning ce^n where c is constant  

c)2^n

d)(logn)^n-1 = e^[(n-1)loglogn]

clearly from above b>a>c

Now to compare a and d ,we compare power of both because they both are exponential function

(n-1)loglogn > n for large value of n therefore we can say that d>b hence option D is correct answer
edited by
–1 votes
–1 votes

Take log for all functions and n=16, n=21024

Case 1:n=16

log( en/n) = n log e - log n=16-4

log (en-0.9logn) =16-(0.9*4)

log(2n)=16

log((log n)n-1)=log(15*(log 24))=log (15*4)=5.9

Case 2:n=21024

log( en/n) = n log e - log n=21024-1024

log (en-0.9logn) =21024-(0.9*1024)

log(2n)=21024

log((log n)n-1)=log(1023*(log 210))=log (1023*10)=13.32

fastest growth will be 2n

So, ans  (C)

edited by
Answer:

Related questions

49 votes
49 votes
7 answers
4