[Math] How to prove the $\Theta$ notation

algorithmsasymptotics

I know that to prove that f(n) = $\Theta$(g(n)) we have to find c1, c2 > 0 and n0 such that

$$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$$

I'm quite new with the proofs in general.

Let assume that we want to prove that $$an^2+bn+c=\Theta(n^2)$$
where a,b,c are constants and a > 0

I'll start with

$$0 \le c_1 \le a + \frac{b}{n} + \frac{c}{n^2} \le c_2$$

In the book I'm reading, they found $c_1 = a/4, c_2 = 7a/4, n_0 = 2*max(|b|/a, \sqrt{|c|/a})$

How ? I'm really lost. What is the approach for this kind of problems ?

Best Answer

The intuition is to make $\frac{\left|b\right|}{n} \le \frac{a}{2}$ and to make $\frac{|c|}{n^2} \le \frac{a}{4}$. That way, you can show the following inequality:

$$ \frac{a}{4} = a - \frac{a}{2} - \frac{a}{4} \le a+\frac{b}{n}+\frac{c}{n^2} \le a + \frac{a}{2} + \frac{a}{4} = \frac{7a}{4}$$

Therefore, let $c_1 = \frac{a}{4}$ and $c_2 = \frac{7a}{4}$. It suffices to find an appropriate $n_0$.

In order to satisfy $\frac{\left|b\right|}{n} \le \frac{a}{2}$, it follows that $n \ge \frac{2|b|}{a}$. Similarly, in order to satisfy $\frac{|c|}{n^2} \le \frac{a}{4}$, it follows that $n^2 \ge \frac{4|c|}{a}$ (or equivalently $n \ge 2\sqrt{\frac{|c|}{a}}$). Therefore, we must have:

$$n \ge \max\left(\frac{2|b|}{a}, 2\sqrt{\frac{|c|}{a}}\right) = 2 \cdot \max\left(\frac{|b|}{a}, \sqrt{\frac{|c|}{a}}\right)$$

The General Case

This approach works very well for arbitrary polynomials. Let $$p(n) = \sum_{i=0}^k a_i n^i$$ where $a_k > 0$. Then, to show that $p(n) \in \Theta\left(n^k\right)$, one can show that $c_1 = \frac{1}{2^k}a_k$ and $c_2 = \left(2-\frac{1}{2^k}\right)a_k$ are both valid constants for $n \ge n_0$, where $$n_0 = 2 \cdot \max\left\{\sqrt[i]{\frac{\left|a_i\right|}{a_k}} \mathrel{}\mathclose{}\middle|\mathopen{}\mathrel{} 0 \le i \le k-1 \right\}$$