How do I find Big O notation for this function?
How do I find Big O notation for this function? $$ n^4+100\cdot(n^2)+50 $$ In the book I am following, I got the following solution:
$n^4+100(n^2)+50 \leq 2(n^4) \ \forall \ n \geq 11$
$n^4+100(n^2)+50=O(n^4)$ with $c=2$ and $n_0=11$
How can I come to know that I have to choose $2(n^4)$ and proceed further?
$\endgroup$ 13 Answers
$\begingroup$The biggest term in this polynomial is $n^4$, so you have to choose a term bigger than $n^4$. Since $2n^4 > n^4$, you can choose $2n^4$ to find some constant $n_0$ where $n > n_0 \implies f(n) \leq 2n^4$. In this case, $n_0=11$.
However, you didn't have to pick $2n^4$. For example, you could've picked $3n^4$ since $3n^4 > n^4$. In this case, we find $n_0=8$. Thus, $c=3$ and $n_0=8$ and this solution works just as well as theirs.
Thus, you don't have to pick $2n^4$. You just need to pick $cn^4$ for some constant $c$ where $cn^4 > n^4$ and thus any $c > 1$ would've worked.
$\endgroup$ $\begingroup$Well, you can basically take a guess for $c$. Notice if you were to take a larger $n$, you could make $c$ smaller. But $2$ seems right, so let's try that. You could then graph $2n^4$ and $n^4 + 100n^2 +50$ and see that our desired inequality holds for all $n\geq 11$.
$\endgroup$ $\begingroup$Well you shouldn't care actually. As $n$ gets bigger, all terms $n^i$ with $i<4$ are negligible when compared to $n^4$ (This is because $\lim_{n \rightarrow \infty} \frac{n^i}{n^4} = 0$ when $i<4$). Hence, you know that starting from a certain $n_0$ (you don't have to know its value yet), $n⁴ + 100n² + 50 < c n^4$ (for any $c>1$ you want).
And for any $c$ you choose, your job is to find the corresponding $n_0$ (actually, "any corresponding $n_0$", because there are infinitely many, and you are not required to find the lowest one).
You can thus choose $c=2$, and you can find $n_0$ by solving the inequality for example. An easier way to do this, would be to try any positive value of $n_0$; if your inequality holds, that's fine, the ($c$,$n_0$) tuple works great, otherwise, just double it (or multiply it by a million, or anything greater than $1$, as many times as needed to satisfy the inequality - you know that you will eventually satisfy it).
$\endgroup$
