1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JTK Mar 16 '15 at 15:52
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Mar 16 '15 at 15:58
  • $\begingroup$ Yeah, this is similar to the way I was shown in class, thank you. $\endgroup$ – JTK Mar 16 '15 at 16:49
  • 1
    $\begingroup$ 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). $\endgroup$ – André Nicolas Mar 16 '15 at 16:52
  • $\begingroup$ 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? $\endgroup$ – JTK Mar 16 '15 at 17:18
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.