2
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – Labbiqa
    Sep 17, 2016 at 14:06
  • $\begingroup$ @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$. $\endgroup$ Sep 18, 2016 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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