Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Hint: take log's. –  David Speyer Nov 27 '11 at 18:35
    
@DavidSpeyer I tried log, but it also confused a bit, see the example above –  LifeH2O Nov 27 '11 at 18:40
add comment

1 Answer

up vote 2 down vote accepted

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. $$

share|improve this answer
    
What about my second example? –  LifeH2O Nov 27 '11 at 18:59
    
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). –  David Mitra Nov 27 '11 at 19:14
    
It was not n, it was n^5 –  LifeH2O Nov 27 '11 at 19:50
    
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$). –  Robert Israel Nov 27 '11 at 19:51
    
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)$. –  David Mitra Nov 27 '11 at 19:56
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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