0
$\begingroup$

In Introduction to Algorithms by CLRS, it's said

For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, we take constants $c_1=a/4, c_2=7a/4$ and $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}).$ You may verify that $0\leq c_1n^2\leq an^2+bn+c \leq c_2n^2$ for all $n\geq n_0.$

They didn't specify how values of these constants came? I tried to prove it but couldn't.

$\endgroup$

1 Answer 1

1
$\begingroup$

I think I can suggest more easy way. Having $a>0$ in $f(n)=an^2+bn+c$ we can take any $a_1<a$ and then show that $a_1n^2 < an^2+bn+c$ for some $N_1,n>N_1$ , because it is same as $a_1 < a + \frac{bn+c}{n^2}$.

Same we can make for any $a<a_2 \Rightarrow an^2+bn+c < a_2n^2$ for some $N_2,n>N_2$ because it is same as $a + \frac{bn+c}{n^2}< a_2$.

At last we will have $a_1n^2 <an^2+bn+c < a_2n^2$.

$\endgroup$

Your Answer

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