[Solved]: Trouble understanding how to pick constants to prove big theta

Problem Detail: 

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.

Asked By : Harrison Nguyen

Answered By : p.j

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14326