Big $O$ small $o$ notation True or False

Question

I'm stuck on a few big-$O$ and small $o$ notation True or False questions, any insight would be appreciated.

$4n^3+6n+17=O(n^4)$ True. The degree of complexity is directly related to n, but it is not represented there. The function grows much faster (left side is like n^2, since it grows faster).

$4n^3+6n+17=O(n^2)$ I think this is false, but no idea why

$n^{17}=o(2^n)$ True. if n^17 increase by 1, an increase is no more n^18, whereas if 2^n increase by 1, an incease is double: 2^n+1. Somewhere 2^n begans to grow faster, because small o notion includes funkction, that grows only slower like in this case.

$5^n=o(3^n)$ False. if lim n->inf (5^n / 3^n) = 0. Since(5^n / 3^n) = (5/3)^n and since for any 0 <= x < 1, lim n->inf (x^n) = 0, is false 5^n = o(3^n).

Is here anything correct?

Answer 1

Think again for the first case. $4n^3+6n+17 = \mathcal{O}(n^4)$ implies that

$$ 4n^3+6n+17 \leq C n^4 $$

for some real number $C$. Divide both sides by $n^4$:

$$ \frac{4}{n}+\frac{6}{n^3}+\frac{17}{n^4} \leq C $$

You will notice that as $n$ approaches $0$, the left hand side shoots off to $\infty$, and therefore cannot be bounded by a real number $C$.

Hint for the second case:

Take the same approach as above and then take $n = C$. You will see that the left hand side can be greater than the right hand side, rendering the inequality to be false.

Answer 2

[When using this notation, it is important to specify which limit you are thinking about. I assume from your attempted solutions that you mean $n\to\infty$.]

You have got the correct answers. For the second one, you're right that it is false. How can you prove it? Suppose it's true. $$4n^3+6n+17=O(n^2)$$ Then $\exists M$ such that for sufficiently large $n$, $$4n^3+6n+17\le Mn^2\\4n+\frac6n+\frac{17}{n^2}\le M$$ Clearly LHS grows unboundedly, so this is not true.