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.
Best Answer
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?