I am trying to understand Big-$O$ notation through a book I have and it is covering Big-$O$ by using functions although I am a bit confused. The book says that $O(g(n))$ where $ g(n)$ is the upper bound of $f(n).$ So I understand that means that $g(n)$ gives the max rate of growth for $f(n)$ at larger values of $n$.
And that there exists an $n_0$ where the rate of growth of $cg(n)$ (where $c$ is some constant) and $f(n)$ have the same rate of growth.
But what I am confused is on these examples on finding Big $O$ in mathematical functions.
This book says find the upper bound for $f(n) = n^4 +100n^2 + 50$ they then state that $n^4 +100n^2 + 50 \leq 2n^4$ (unsure why the $2n^4$) then they somehow find $n_0 =11$ and $c = 2$, I understand why the big $O$ is $O(n^4)$ but I am just confused about the rest.
This is all discouraging as I don't understand but I feel like this is an important topic that I must understand.
If any one is curious the book is Data Structures and Algorithms Made Easy by Narasimha Karumanchi
Not sure if this post belongs here or in the stack overflow board.
Best Answer
Suppose you have two functions $f$ and $g$. We say $f(n)$ is $O(g(n))$ or $f$ is $O(g)$ if $\exists C, n_0 $ such that $\forall n \geq n_0 $ we have $f(n) \leq C g(n)$. This is to formalize that the function $f$ grows at a slower rate than the function $g$ for large $n$.
For the function you gave: $ f(n) = n^4 +100n^2 + 50 $, we need to show $f$ is $O(n^4)$. To show this, proceeding from how we defined this notion, we must find a constant $C$ and natural number $n_0$ so that $n^4 +100n^2 + 50 \leq C n^4$ $\forall n \geq n_0$. Now you can check that $n_0 =11, c=2$ does the job. There is no uniqueness to these constants as any $c>2$ and any $n_0 > 11$ will also work.
Hope this helps.