Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Note than $n$ is a parameter for the functions.

For some constants $c_1, c_2$ and $n_0,$$$c_1n^2\le an^2 + bn + c \le c_2n^2$$ for all n > $n_0$.

Consider any quadratic function $f(n) =an^2 + bn^2 + c$, where $a, b$, and $c$ are constants and $a > 0$. Throwing away the lower-order terms and ignoring the constant yields $f(n) = \Theta(n^2)$. Formally, to show the same thing, we take the constants $c_1 = a/4$, $c_2 = 7a/4$ and $n_0 = 2 \cdot\max(\lvert b\rvert / a, \sqrt{\lvert c\rvert/a})$.

Q1: How were $c_1, c_2, n_0$ derived? They seem to be arbitrary. The book does not provide any kind of explanation on how they are derived.

For some constant $c, n_0$ $$0\le cn \le n^2$$ for all $n$ > $n_0$

This can be seen by taking $c = a+ \lvert b \rvert$ and $n_0 = \max(-1, -b / a)$

Q2: How was $c, n_0$ derived? Again they seem to be arbitrary and lack an explanation.

share|improve this question
    
Very likely they were derived by trial-and-error. Also note that in your first question, there are infinitely many values of $c_1$ and $c_2$ which will work. –  Code-Guru Dec 14 '12 at 3:57
    
In your second question, where do $a$ and $b$ come from? –  Code-Guru Dec 14 '12 at 4:00
add comment

2 Answers

There was no trial or error involved. they just wanted a uniform treatment. With $a > 0,$ we have $$ a n^2 + b n + c = a n^2 \left( 1 + \frac{b}{an} + \frac{c}{a n^2} \right) . $$ Now, if $ n \geq \frac{2 |b|}{a}, $ we find $$\left| \frac{b}{an} \right| \leq \frac{1}{2}.$$ If we also have $ n \geq 2\sqrt{ \frac{ |c|}{a}}, $ we find $$\left| \frac{c}{an^2} \right| \leq \frac{1}{4}.$$ If both inequalities hold (compare $n_0$) then $$ \frac{1}{4} \leq \left( 1 + \frac{b}{an} + \frac{c}{a n^2} \right) \leq \frac{7}{4} . $$

EXERCISE: What would happen if you replaced the 2 in the definition of $n_0$ with a 3?

share|improve this answer
add comment

They are arbitrary. In fact, there are infinitely many combinations of these constants that satisfy the given inequalities.

The whole point of all these is not about the exact values of the constants, but that the order of magnitude of $an^2+bn+c$ grows like that of $n^2$ when $n$ is large, and the order of magnitude of $n$ does not out-grow the order of magnitude of $n^2$. As long as you can prove these facts, we don't care what constants are chosen in the proofs.

You may pick other constant values than those specified by your textbook. For instance, choose at will a value for $c_1$ with $0<c_1<a$. If $b^2-4(a-c_1)c<0$, then the quadratic equation $(a-c_1)n^2+bn+c=0$ has no real root and hence $c_1n^2\le an^2+bn+c$ is automatically true for all values of $n$. So, any choice of nonnegative $n_0$ would be valid. If $b^2-4(a-c_1)c\ge0$, then the two roots of $(a-c_1)n^2+bn+c=0$ are $-b\pm\sqrt{b^2-4(a-c_1)c}$. So, you may pick any nonnegative $n_0$ that is larger than or equal to $-b+\sqrt{b^2-4(a-c_1)c}$. That your textbook opted to pick another value of $c_1$ is perhaps because the author wanted to avoid splitting the proof into two cases according to the sign of the discriminant $b^2-4(a-c_1)c$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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