0
$\begingroup$

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.

  • 0
    In your second question, where do $a$ and $b$ come from?2012-12-14

2 Answers 2

1

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?

1

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. 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$.