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've been struggling with a homework-like problem (I'm a self-studier) and having trouble understanding the 'hints' I've already received. Please forgive my lack of knowledge around terminology.

Let's say I have this list of functions and I want to order them by increasing order of growth rate:

$$ n^2 $$ $$ n^2 \log(n) $$ $$ 2^n $$

The two 'hints' I have are 'graph for large values of n' and 'take logarithms and see what happens'.

I have tried graphing these, but I'm not sure how to interpret my findings (because I keep ending up with the wrong answers). I fear I must be doing something really incorrect.

I don't want the answer here, but I'd like a push towards the right approach.

Thanks for your understanding. I'm having some real trouble with the basics. Even an example as to how to 'take the logarthims' of these would help me a lot.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Taking logarithms can be useful because of the fact that if $x$ and $y$ are positive real numbers, then $x<y$ if and only if $\log x<\log y$, and sometimes the logarithms are easier to compare. For example, basic properties of the logarithm tell us that $\log n^2 = 2\log n$ and $\log 2^n=n\log 2$. Now look at a graph of $y=2\log x$: it rises as $x$ increases, but it also gets flatter and flatter, meaning that it’s rising more and more slowly. What about the graph of $y=(\log 2)x$? Does it get flatter as it rises, or does it keep rising at a constant slope? Which one will eventually get on top and stay there? In fact, it won’t just stay on top: it’ll keep getting further and further above the other one, so it must be growing faster.

That should help you with the comparison of $n^2$ and $2^n$. The comparison of $n^2$ with $n^2\log n$ is easier. Just look at the ratio of the two, $$\frac{n^2\log n}{n^2}=\log n\;.$$ As $n$ increases, what happens to that ratio? Does it get smaller, approach some limiting value, or get bigger? If it gets bigger, you know that the numerator, $n^2\log n$, must be growing faster than the denominator, $n^2$. If it’s roughly constant, they must be growing at about the same rate. And so on.

That leaves the comparison between $n^2\log n$ and $2^n$. Logarithms can again help here: $\log(n^2\log n)=\log n^2+\log(\log n)=2\log n+\log(\log n)$, again using basic properties of the logarithm. How does that compare with $n\log 2$, the logarithm of $2^n$, when $n$ is very large?

share|improve this answer
    
Thank you .. that's very helpful ! –  duckus Mar 17 '12 at 17:31

Since the logarithm function is monotone increasing, a function $f$ grows faster than $g$ iff $\log(f)$ grows faster than $\log(g)$. In order to "take logarithms," remember the important property of $\log$: $\log(ab)=\log(a)+\log(b)$, and so $\log(a^b)=b\log(a)$. Applying to your particular case, you should get

1) $\log(n^2)=2\log(n)$

2) $\log(n^2\log(n))=2\log(n) + \log\log(n)$

3) $\log(2^n)=n\log(2)$

Now it is easy to compare 1 with 2 and 1 with 3. The only one that isn't immediately obvious is comparing 2 with 3, but it's a linear function vs the sum of two logarithms so it's not so bad.

share|improve this answer

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.