4
$\begingroup$

So I'm reading Introductions to Algorithms and sometimes I wish it would be a little bit more friendly with how it explains topics. One of these topics is proving big-theta.

I understand that the definition of $\Theta$ is as follows:

$\Theta(g(n)) = f(n)$ if there exists positive constants $c_1$, $c_2$, and $n_0$ such that $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$.

In other words, for $f(n)$ and $g(n)$, $f(n)$ can be bounded by $c_2 g(n)$ from above and bounded below by $c_1 g(n)$.

So the example in the book goes:

Show that $\frac{1}{2} n^2 - 3 n = \Theta(n^2)$.

From the definition of big theta:

$$ c_1 n^2 \le \frac{1}{2} n^2 - 3 n \le c_2 n^2$$

CLRS begins by dividing by the largest order term of $n$ which is $n^2$ to get

$$ c_1 \le \frac{1}{2} - \frac{3}{n} \le c_2 $$

From here we split the problem into two parts, the right-hand inequality and the left-hand inequality.

On the right hand side: CLRS chooses $c_2 \ge \frac{1}{2}$ because for $n \gt 1$, $\frac{1}{2} - \frac{3}{n}$ can never be less than $\frac{1}{2}$ since $\frac{3}{n}$ goes to $0$ as $n$ goes to infinity. (I'm assuming they choose $n \gt 1$ here because if $n=0$ then we would be dividing by $0$.)

Now this is where I start to get lost.

On the left hand side: CLRS chooses $c_1 = \frac{1}{14}$ (not sure why) and $n \ge 7$. I'm not sure what the significance of these choices is. At $n \le 6$, $\frac{1}{2}-\frac{3}{n}$ becomes negative. But why $\frac{1}{14}$ for $c_2$? I'm just not sure how they arrived at solving the left hand side and the book doesn't really explain it well for me.

$\endgroup$
  • $\begingroup$ on a different note, can I suggest you to take a look at the Kleinberg and Tardos Algorithm Design or this freely available book by Dasgupta et.al. I personally prefer both these books to CLRS because of the language and flow of the book, I found both these books to be more 'fun' than CLRS. 'Fun' : can be used as self-study book, very readable, and creates a strong foundation and appreciation of the beauty and joy of algorithms. $\endgroup$ – Subhayan Sep 15 '13 at 10:51
5
$\begingroup$

For $n \leq 6$, $$ 1/2 - 3/n \le0, $$ so if you are taking integer value of $n$, put $n = 7$ as it gives $1/14$. This is how he arrived in the conclusion i.e., for $n \geq 7$, $$ 1/2 - 3/n \ge1/14, $$ because $n$ is in the denominator it will only decrease the value of -ve term, so overall value will increase with $n$, which is the constant $c_1$.

$\endgroup$
  • $\begingroup$ Thank you. This makes so much more sense now. I think the problem with CLRS(for me) is that it assumes you're really smart, and while I'm trying to be - I want to learn as seamlessly as possible while not getting stuck on such trivial matters. $\endgroup$ – Harrison Nguyen Sep 15 '13 at 17:24
  • $\begingroup$ @HarrisonNguyen don't feel bad if you stuck somewhere, I would say feel good, thinking that now you are going to learning something..:) $\endgroup$ – p.j Sep 15 '13 at 18:18
  • $\begingroup$ @HarrisonNguyen Finding "suitable constants" is a matter of exercise ("I see that ... will work.") and, more importantly, iteration: you try some, fail, and adjust. Repeat this until you have constants that work. No magic there, only diligence. $\endgroup$ – Raphael Sep 16 '13 at 8:15

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.