Big-O notation examples

Question

How do I get c = 4 and n0 = 21, I understand that I could plug in different numbers till f(n) ≤ c * n for all n ≥ n0, but using f(n) how do I arrive at those numbers?

3n^3 + 20n^2 + 5
3n^3 + 20n^2 + 5 is O(n^3)
need c > 0 and n0 ≥ 1 such that 3n^3 + 20n^2 + 5 ≤ c*n^3 for n ≥ n0
this is true for c = 4 and n0 = 21 

I'm also struglling to get my head around this one,

3 log n + 5
3 log n + 5 is O(log n)
need c > 0 and n0 ≥ 1 such that 3 log n + 5 ≤ c*log n for n ≥ n0
this is true for c = 8 and n0 = 2

Answer 1

We first show how to obtain the numbers mentioned for $3n^3+20n^2+5$. If $n\ge 2$, then $20n^2+5\le 21n^2$. And if $n\ge 21$ then $21n^2\le n^3$. So if $n\ge 21$ then $3n^3+21n^2+5\le 4n^3$.

Remark: I would not have shown that $3n^3+20n^2+5$ is $O(n^3)$ in this way. Here is an alternative less thinking way. If $n\ge 1$ then $20n^2\le 20n^3$ and $5\le 5n^3$. It follows that if $n\ge 1$ then $3n^3+20n^2+5\le 3n^3+20n^3+5n^3=28n^3$. A much cruder upper bound, but it does the job!

For $3\log n +5$, I will assume that since this seems to be from a discrete math for Computer Science course, the logarithm is to the base $2$. If $n\ge 32$ then $\log n\ge 5$. It follows that if $n\ge 32$ then $3\log n+5\le 4\log n$. If another $\log$ is intended, for example $e$, then $32$ can be replaced by any integer greater than $e^5$.

Answer 2

Of course, the values of $C$ and $n_0$ are not at all unique for any examples. But let's see the reasoning that leads to the numbers given in the first example:

At a glance, you can see that $f(n) = 3n^3 + 20n^2 + 5$ will always exceed $3n^3$ for positive $n$, so $C$ will have to be somewhat greater than $3$. As a convenient number more than $3$ try $C=4$. Then $$4n^3-f(n) = n^3 - 20n^2 - 5$$ So when is $n^3 > 20n^2 + 5$? Well, that is equivalient (divide by $n^2$) to $$ n > 20 + \frac{5}{n^2}$$ and it is easy to see (and prove) that this holds for all $$n \geq n_0 = 21$$

The same logic for the second example would say we could use $C = 4$ and $n_0 = \lceil e^5 \rceil = 149$. The proposed set of $C,n_0$ is in fact wrong; for $C=8$, $n_0$ must be at least 3.

Answer 3

If you say that $f(n)$ is $\mathbb O (g(n))$ then you have to prove that the quotient $\frac{f(n)}{g(n)}$ tends to a constant whose absolute value is greater than zero. (If it is zero then we are talking about the little oh!.)

In the cases, you listed we have:

(1) $$\lim_{n \rightarrow +\infty }\frac{3n^3+20n^2+5}{n^3}=3+\lim_{n \rightarrow +\infty }\left(\frac{20}{n}+\frac{5}{n^3}\right)=3.$$

Here the constant is $3$. Furthermore, for any $\epsilon>0$ there is an $n_0$, such that for all $n>n_0$, $\frac{20}{n}+\frac{5}{n^3}<\epsilon.$ Let $\epsilon$ be $1$. Obviously, for $n>21$: $\frac{20}{n}+\frac{5}{n^3}<1.$ So for any $n>21$ $$3n^3+20n^2+5<4n^3.$$

(2) $$\lim_{n \rightarrow +\infty }\frac{\log(n)+5}{\log(n)}=1+\lim_{n \rightarrow +\infty }\frac{5}{\log(n)}=1.$$ If $n\ge 6$ then $\frac{5}{\log(n)}<7.$ So,$$\log(n)+5<8\log(n).$$