Show that $f(n)=n^3+20n+1=O(n^3)$

Question

In my theoretical CS class we covered Big $O$-notation and I had some problems that needed to be solved.

Show that

$$f(n)=n^3+20n+1=O(n^3)$$ $$l(n)=n^3+20n+1≠O(n^2)$$ $$h(n)=n\sqrt{n}=O(n^2)$$

The rule states that $f(n)\leq C*g(n)$, so for the first question it's

$$n^3+20n+1 \leq C*n^3$$

$$1+\frac {20}{n^2}+\frac {1}{n^3} \leq C$$

As $n$ increases to infinity, the left side approaches $1$. Here's where it's confusing. Since the left side would approach infinity, wouldn't the equation become $1 \leq C$? But the answer says that the answer is $22 \leq C$

For $l(n)$ I did the same thing as above but then it's obvious that no matter what the input of $n$ it will approach infinity and not a constant.

For $h(x)$ I showed that

$$n\sqrt{n} \leq C*n^2$$

$$\frac{n\sqrt{n}}{n^2} = \frac {\sqrt{n}}{n} \leq C$$

As $n$ increases $h(n)$ decreases and eventually approaches $0 $ as $n$ approaches inifity. So how can I show that $n\sqrt{n}=O(n^2)$?

Answer 1

Note that for $$1+\frac {20}{n^2}+\frac {1}{n^3} \leq C$$ the LHS decreases as $n\to\infty$. Since you want the maximum of LHS, you find it when $n=1$, which gives $$C\ge 1+20+1=22$$

Suppose $$l(n)=n^3+20n+1=O(n^2)$$ Then on dividing by $n^2$, we get $$n+\frac{20}n+\frac1{n^2}\le C$$ which is impossible since $\{n\}$ diverges as $n\to\infty$.

Finally we deal with $h(n)$. Write it as $$n^{3/2}=O(n^2)\iff \frac1{\sqrt n}\le C$$ Similarly, since LHS decreases, we need only find it when $n=1$; that is $$C\ge1$$

Answer 2

For $n \ge 1$, $$\frac{20}{n^2} \le 20 \quad ; \frac{1}{n^3} \le 1 \implies 1+\frac{20}{n^2}+\frac{1}{n^3} \le 22 $$

Not that $\displaystyle \lim_{n \to \infty} 1+\frac{20}{n^2}+\frac{1}{n^3} =1$ is lower bound for the function, not for $C$. For boundness of $C$, we need to find maximum value of given fucntion.

Answer 3

To answer to your first question, even if the left-hand side approaches infinity, the constant has to be greater or equal to each of the values of $n$. In particular $$ 1+ \frac{20}{n^2} + \frac{1}{n^3}$$ is a decreasing function in $n$, so that for $n=1$ we get the least $C$ that satisfies the inequality, ergo $1+20+1=22$.

About $h(n)$, notice that for $C=1$ the inequality $$ \frac{\sqrt{n}}{n}\leq C$$ is always true, so that $h(n)=O(n^2)$.

Answer 4

To show that $f(n)=O(n^3)$ the following is sufficient:

$n^3+20n+1\le n^3+20n^3+n^3=22n^3,n\ge 1$

$h(n)=n\sqrt{n}=O(n^2)$:

$n\sqrt{n}\le n*n=n^2,n\ge 1$

$l(n)=n^3+20n+1\neq O(n^2)$:

If it were $O(n^2)$ each of $n^3$, $20n$ and $1$ would have to be less than $Cn^2$ for a fixed $C\in\mathbb{R^+}$ for all $n$ to infinity. Clearly this is impossible for $n^3$.