# Compare growth rate of functions (exponential vs. polynomial)

I have to compare the growth rate of the following sequences

$a_n=a_{n-1}=10$

$b_n=\sum_{k=1}^n k^2$

$c_n =\frac{n^2}{10}$

$d_n=\left( \frac{3}{2} \right)^n$

I've rewritten $b_n$ and $d_n$ to

$$b_n = \frac{1}{6} (2n^3+3n^2+n) \quad \text{and} \quad d_n=1.5^n$$

and would say that $a_n = \mathcal{O}(1)$, $b_n = \mathcal{O}(n^3)$, $c_n = \mathcal{O}(n^2)$ and $d_n = \mathcal{O}(1.5^n$).

When sorting them, it should be

$$a_n < c_n < b_n < d_n$$

Here is the part, that I do not get. When graphing the functions or simply calculating, I get that $\mathcal{O}(1.5^n)<\mathcal{O}(n^2)$. Since $(k^n=)1.5^n$ is an exponential function with $k>1$, it should have a growth greater than the polynomial function $n^2$. I can't seem to figure out which of the 2 options is the right one.

Any help with explanation would be appreciated.

• You got it wrong for $b_n$ Sep 17, 2016 at 12:19
• @polfosol is it the explicit expression for the sum or the growth rate? Sep 17, 2016 at 12:21
• Just to clarify, in the description of $b_n$ is it $k=1$ as the lower bound of the summation rather than $k-1$? Sep 17, 2016 at 12:21
• @ParclyTaxel Yes, it should be $k=1$. Thanks. Corrected. Sep 17, 2016 at 12:22
• @Labbiqa: The explicit expression and consequently, the growth rate are both wrong Sep 17, 2016 at 12:29

That $\mathcal O(1.5^n)$ seems to grow slower than $\mathcal O(n^2)$ (or $\mathcal O(n^3)$) is an illusion. Exponential functions with exponents greater than 1 grow faster than all polynomial functions, but only eventually.
This is the key word: growth rates describe limiting behaviour, not behaviour at a particular point. In particular, the point where $1.5^n$ overtakes $n^2$ in growth was off your graph, and you missed it.
• Thanks for the clarification. I thought it was odd since no matter how much I zoomed out, it still didn't grow faster than $\mathcal{O}(n^2)$. Sep 17, 2016 at 14:06
• @Labbiqa, the graphs for $n^2$ and $1.5^n$ cross at about $n\approx 12.5$. Take a look at their graphs over an interval like $1 < n < 20$. Sep 18, 2016 at 13:39