2

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.

Parcly Taxel
  • 103,344
Labbiqa
  • 135

1 Answers1

2

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.

Parcly Taxel
  • 103,344
  • 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)$. – Labbiqa Sep 17 '16 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$. – Antonio Vargas Sep 18 '16 at 13:39