0
$\begingroup$

I was given homework to sort some (14) functions in order of their growth rate. I am confused about two functions $3^\sqrt{\log n}$ and $n^{\log n}$: about where these two lie within those 14 functions.

I tried wolframalpha but it does not plot the graphs well and is not very useful. Which technique I should use to compare growth rates of functions?

EDIT:
I tried taking logs, but it also confused at places. For example I have taken double logs below

log(5) + log(log(n)) AND log(log(5n+20))

I don't know which one is bigger here

  • 2
    Hint: take log's.2011-11-27
  • 0
    @DavidSpeyer I tried log, but it also confused a bit, see the example above2011-11-27

1 Answers 1

2

You could just compare the two functions. The base 3 is constant and the base $n$ tends to infinity. Now compare the exponents: $\sqrt{\log n}$ grows more slowly than $\log n$. These two observations imply that $3^{\sqrt{\log n}}$ grows more slowly that $n^{\log n}$.

In fact, for $n>10$: $$ { n^{\log n}\over3^{\sqrt{\log n}}}\ge { 10^{\log n}\over3^{\sqrt{\log n}}} \ge{ 10^{\log n}\over3^{ \log n }}={(10/3)^{\log n}}\rightarrow\infty. $$

  • 0
    What about my second example?2011-11-27
  • 1
    There, you need to compare the growth rates of $n$ and $5n+20$. They grow at the same rate since ${n\over 5n+20}={1\over 5+{20\over n}}\rightarrow {1\over 5}$. Since these grow at the same rate, so will their logarithms (and adding $\log 5$ to one won't change that fact).2011-11-27
  • 0
    It was not n, it was n^52011-11-27
  • 0
    Although the growth rates are the same, $\log \log(5 n + 20) < \log (5) + \log \log(n)$ for large $n$ (in fact for $n \ge 2$).2011-11-27
  • 0
    You meant $\log (5)+\log(\log(n))$ and $\log(\log(n^5+20))$? Then $\log(\log(n^5+20))$ grows as fast as $\log(\log(n^5))= \log (5\log n)=\log 5 +\log(\log n)$.2011-11-27
  • 0
    By "grows as fast as", I mean the quotient tends to a non-zero number. If you just want to see which is bigger: $\log(\log(n^5+20))>\log(\log(n^5))=\log 5+ \log(\log(n))$. Sorry for the confusion.2011-11-27
  • 0
    @DavidMitra Thanks, Although I stated it wrong by saying n^5 but I understood which one is bigger correctly.2011-11-28