1

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
JTK
  • 137

3 Answers3

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$.

André Nicolas
  • 507,029
  • I follow your second solution to the first problem, but had one question, why did you drop the 3 from 3n^3 is this a typo? – JTK Mar 16 '15 at 15:52
  • Yes, there were some typos. Was outside (smoking) and it is sunny (yeah!) so I could barely see the screen. Typos fixed, I think. Not much change, $26n^3$ gets replaced by $28n^3$. – André Nicolas Mar 16 '15 at 15:58
  • Yeah, this is similar to the way I was shown in class, thank you. – JTK Mar 16 '15 at 16:49
  • 1
    You are welcome. In dealing with big $O$ stuff, we really don't want to work too hard getting tight bounds. (Tight bounds become important in more delicate work). – André Nicolas Mar 16 '15 at 16:52
  • For the second problem, your assumption that the logarithm is to the base 2 is correct, but I'm struggling to follow your solution, you got 32 from (3 log n +5), but I cant see how you arrived at 4 log n, also how do I get n0 = 2? – JTK Mar 16 '15 at 17:18
  • First a notation comment. I assumed you meant $3\log n+5$. The details would be different if you meant $3\log(n+5)$. If $n\ge 32$, then $\log n\ge \log(32)=5$, since $32=2^5$. So if $n\ge 32$ then $3\log n+5\le 3\log n+\log n= 4\log n$. – André Nicolas Mar 16 '15 at 17:43
1

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.

Mark Fischler
  • 41,743
1

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).$$

zoli
  • 20,452