How would I approach solving this Little Oh problem?

Question

$2n + 10 \in o(n^2)$.

My understanding of Little Oh is that for any positive constant $c$, there exists a constant $n_0 > 0$ such that $f(n) \leq c\cdot g(n)$ for all $n > n_0$.

How I think I should do it is:

Plug the functions in as:

• $2n+10 \leq cn^2$

and try to solve for n. But I get stuck here:

• $(2n+10)/n^2 \leq c$
• $2/n + 10/n^2 \leq c $

EDIT: An answer in my notes is $n$ > $n_0$ > $(20/c)$^(1/2) and $4/c$. I have no idea how to arrive at that answer.

Answer 1

"But I get stuck here: $2/n + 10/n^2 \leq c.$ An answer in my notes is $n>n_0>(20/c)^{1/2}$ and $4/c$. I have no idea how to arrive at that answer."

You were on the right track. A (not necessary but) sufficient condition for $$2/n + 10/n^2 \leq c$$ is to have both $$2/n\leq c/2\quad\text{and}\quad10/n^2 \leq c/2,$$ i.e. both $$n\ge4/c\quad\text{and}\quad n^2\ge20/c,$$ which is equivalent to$$n\ge\max(4/c,(20/c)^{1/2}).$$

Answer 2

You seem to ask two different questions, so I'll just answer the question you were trying to solve.

Prove that $2n+10 \in o(n^2)$. I'll start as you did, let $c> 0$, then

$$2n+10<cn^2 \iff \frac{2n+10}{n^2}\leq c \iff \frac{2}{n}+ \frac{10}{n^2}\leq c$$

Here please observe that you had a mistake in the last implication, but also observe that you really need the if and only if in each step.

Thus, to prove the claim we need to show that for every $c>0$, there exists $n_0$ such that for all $n_0>n$ we have $\frac{2}{n} + \frac{10}{n^2}\leq c$. To do this either use the fact that $\lim_{n\rightarrow\infty}\frac{2}{n} + \frac{10}{n^2} = 0.$