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.

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

1 Answer 1


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

  • $\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$ Commented Sep 15, 2013 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$
    – Parag
    Commented Sep 15, 2013 at 18:18
  • 1
    $\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
    Commented Sep 16, 2013 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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