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
$\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, privacy policy and cookie policy

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