Dealing with big O

Question

Is this true or false?

$(n(n+1)(n+2))/6$ is $O(n^3)$ (big O)

I have broken it down to this

$(n^3 + 3n^2 + 2n) / 6$

but am unsure what to do next to prove/disprove this statement.

What does $f(n)=O(n^3)$ mean, according to the definition of $O$? — Arthur, Sep 12 '16 at 15:23

score 1 · Answer 1 · answered Sep 12 '16 at 15:23

1

Hint

Do you think that $$n\longmapsto \frac{\frac{n^3+3n^2+2n}{6}}{n^3}$$ is bounded when $n\geq 1$ ?

answered Sep 12 '16 at 15:23

Surb

I would say no? I am mostly confused as to what it means by "is O(n^3)". I am in a class where the professor doesnt show up, so a few of us are trying to teach ourselves with practice problems from the book. – Racehorse35 Sep 12 '16 at 15:28
2

By definition, $$f(n)=O(g(n))$$ if $\left|\frac{f(n)}{g(n)}\right|$ is bounded when $n\to \infty $. My be you should reconsider your answer ;-) – Surb Sep 12 '16 at 15:31

score 0 · Answer 2 · answered Sep 12 '16 at 16:11

Working off of Surb's answer, take

$$\lim_{n \to \infty} \frac{\frac{n^3+3n^2+2n}{6}}{n^3}$$

$$\lim_{n \to \infty} \dfrac{n^3+3n^2+2n}{6n^3}$$

$$\lim_{n \to \infty} \dfrac{n^3}{6n^3} + \dfrac{3n^2}{6n^3} + \dfrac{2n}{6n^3} $$

$$\lim_{n \to \infty} \dfrac{1}{6} + \dfrac{1}{2n} + \dfrac{1}{3n^2} $$

As $n$ approaches $\infty$, $\dfrac {1}{2n}$ and $\dfrac {1}{3n^2}$ both go to zero, so the result is $\dfrac 16$.

2 Answers2