-2
$\begingroup$

Question

I want to arrange which is asymptotically faster -:

$$n^{100},2^{n},n^{\log\,n}$$

My approach

I know that Exponential function will beat Polynomial function from here

but i am thinking of different way of solving it.

let $$f_{1}=n^{100},f_{2}=2^{n},f_{3}=n^{\log n}$$

Take log both sides-:

$$y_{1}=\log f_{1}=100 *\log\,n$$ $$y_{2}=\log f_{2}=n$$

$$y_{3}=\log \,f_{3}=\log\,(\log\,n*n)$$

hence $$f_{2}>f_{3}>f_{1}$$

Am i right?

$\endgroup$
3
  • 1
    $\begingroup$ Yes, this is correct. It works because of the continuity of $\log$ and $\exp$. $$\log f\leq\log g\iff \log\frac fg\leq 0\iff f\leq g$$ $\endgroup$
    – Prasun Biswas
    Oct 6, 2017 at 19:29
  • 1
    $\begingroup$ It seems more straight forward to rewrite your functions using $x = e^{\ln x}$. Then you're just comparing $\{e^{100\ln n}, e^{(\ln 2) n}, e^{(\ln n)^2}\}$. $\endgroup$
    – user474330
    Oct 6, 2017 at 19:31
  • 1
    $\begingroup$ @PrasunBiswas No, it's not correct. $\endgroup$
    – zhw.
    Oct 6, 2017 at 19:42

1 Answer 1

Reset to default
2
$\begingroup$

Take logarithms of the three quantities, it is then clear that (for sufficinetly large $n$) \begin{eqnarray*} 100 \ln n < (\ln n)^2 < n \ln 2. \end{eqnarray*} So your answer should be $ f_1 < f_3 < f_2 $.

$\endgroup$
4
  • 1
    $\begingroup$ That answer has $f_1> f_3,$ $\endgroup$
    – zhw.
    Oct 6, 2017 at 19:35
  • $\begingroup$ @zhw. You are right ... $\endgroup$
    – Donald Splutterwit
    Oct 6, 2017 at 19:39
  • $\begingroup$ @DonaldSplutterwit can you please explain that after taking log of $f_{3}$, it is $(\ln n )^{2}$.I am okk upto $\log \log n \, n$ $\endgroup$
    – laura
    Oct 6, 2017 at 19:46
  • 1
    $\begingroup$ $ \ln (n^m) = m \ln n $ ... now let $m = \ln n$ ... so its $ \ln n \times \ln n$. $\endgroup$
    – Donald Splutterwit
    Oct 6, 2017 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.