# Trouble understanding how to pick constants to prove big theta

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.

• 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. Sep 15, 2013 at 10:51

## 1 Answer

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

• 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. Sep 15, 2013 at 17:24
• @HarrisonNguyen don't feel bad if you stuck somewhere, I would say feel good, thinking that now you are going to learning something..:) Sep 15, 2013 at 18:18
• @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.
– Raphael
Sep 16, 2013 at 8:15