$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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14326
