Finding the upper tight bound of a mathematical function. (Big O)

Question

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.

Answer 1

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.

Answer 2

I know this is old post but I am gonna explain it in a simple way for people who are struggling with it.
we have the function:
$f(n) = n^4 + 100n^2 + 50$
knowing that the upper bound function must satisfy this rule:
$f(n) \le c.g(n)$
we can apply it:
$n^4 + 100n^2 + 50 \le c. n^4$
where $g(n)$ is the $n$ with highest power in $f(n)$ which is in this case $n^4$.
We see in $f(n)$ that $n^4$ has a constant 1:
$f(n)= (1).n^4 + 100n^2 + 50$.

So for $c$ we take any constant that is higher than $1$, which is in this case $2$.
So we know now that $c$ is $2$.
Now to find $n0$, we can guess and apply it to the function to determine if it satisfies:
$f(n) \le c.g(n)$
so assuming $n0 = 1$
$1^4 + 100(1)^2 + 50 \le 2(1)^4$
$151 \le 2$ which is wrong.
We know that $n0$ can't be 1 because it doesn't satisfies the inequality.
Let's try with $n0 = 10$
$10^4 + 100(10)^2 + 50 \le 2(10)^4$
$10000 + 10000 + 50 \le 20000 \Rightarrow 20050 \le 20000 $ which is wrong too.
Let's try now with $n0 = 11$
$11^4 + 100(11)^2 + 50 \le 2(11)^4$
$26791 \le 29282$ which satisfies the inequality.
So we know now that $n0 \ge 11$
Hope this clarifies it.