0
$\begingroup$

I'm Reading Introduction to Algorithms and in the section where they talk about how any quadratic function $$f(n) = an^2 + bn + c$$ where $a$, $b$ and $c$ are constants and $a > 0$

Throwing away the lower-order terms and ignoring constants 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(|b|/a, \sqrt{|c|/a})$

You may verify that $0\le c_1n^2 \le an^2 + bn + c \le c_2n^2$ for all $n > n_0$.

What I don't understand is how they got those constants? Or that value of $n_0$.

Here they already told us

For a given function $g(n)$, we denote by $\Theta(g(n))$ the set of functions

$\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1$, and $c_2$, and $n_0$ such that $0\le c_1g(n) \le f(n) \le c_2g(n)$ $\}$

So how did they get those values for the constants?

$\endgroup$
7
  • $\begingroup$ I am always surprised that texts covering Big-$O$ notation don't just prove that we can replace all the convoluted definitions with simple limits. No need to find constants now; all that is needed is to take a limit (which a first year calculus student can do) $\endgroup$ Commented Feb 22, 2017 at 6:09
  • $\begingroup$ The limit of what exactly? $\endgroup$ Commented Feb 22, 2017 at 6:41
  • $\begingroup$ See here $\endgroup$ Commented Feb 22, 2017 at 6:45
  • $\begingroup$ thank you, that's much easier to understand. $\endgroup$ Commented Feb 22, 2017 at 6:48
  • $\begingroup$ No problem. See, I don't get why most texts don't start by explaining it that way :) that being said, that link doesn't really answer your question. $\endgroup$ Commented Feb 22, 2017 at 6:50

1 Answer 1

1
$\begingroup$

First of all, your question is answered here on Stack Overflow. I have greatly expanded the level of detail in my post compared to that post in more of a Math.SE style, so I feel that my answer is worthwhile regardless of the existing post. Moreover, I had worked much of my post already before finding the existing answer on a different site.


The textbook is choosing loose and convenient constants, and not necessarily tight ones. Let's run through the book's logic. If we set $c_1 = a/4$ then we clearly have $\frac{a}{4}n^2 \ge 0$ in general only when $a\ge0$, so we first set this condition. We next set $c_1g(n)$ and $f(n)$ equal to get $$\frac{a}{4}n^2 = an^2+bn+c\\ \implies n=\pm\frac{2\sqrt{b^2-3ac}-2b}{3a}$$ We clearly want the rightmost root; a simple way to do this is just to take the positive solution. We can thus let $n_0$ be any $$n \ge \frac{2\sqrt{b^2-3ac}-2b}{3a} \tag{1}$$


Let's now look at your book's definition of $n_0$; we see that we can take $\frac{|b|}{a}$ whenever $b^2 \ge a|c|$ by rearranging the inequality $\frac{|b|}{a} \ge \sqrt{\frac{|c|}{a}}$. Clearly we have $|c| \ge -c \implies a|c| \ge -ac$ and thus $b^2 \ge -ac$. Multiply both sides by $3$ and add $b^2$ to both sides to get $4b^2 \ge b^2-3ac$. We can put this into $(1)$ to get $$\frac{2\sqrt{b^2-3ac}-2b}{3a}\le\frac{2\sqrt{4b^2}-2b}{3a}=\frac{2}{3a}(|2b|-b)\le\frac{2}{3a}(3|b|)=2\frac{|b|}{a}$$ Where the second-to-last inequality follows from the parentheses being maximized when $b < 0 \implies b = -|b|$


In the case $a|c| \ge b^2$ we have that $4a|c| = a|c| + 3a|c| \ge b^2 + 3a|c| \ge b^2 - 3ac$ where the last inequality follows again from $|c| \ge -c$. Plugging this into $(1)$, we thus notice that $$\frac{2\sqrt{b^2-3ac}-2b}{3a} \le \frac{2}{3a}(\sqrt{4a|c|}-b)=\frac{2}{3a}(2\sqrt{a|c|}-b)\le \frac{2}{3a}(3\sqrt{a|c|})=2\sqrt{\frac{|c|}{a}}$$

Where the second-to-last inequality follows from the parentheses being maximized when $b = -\sqrt{a|c|}$ similar to above


$c_2$ follows similarly, but this has been enough work to prove already, so I leave this up to the OP.


Addendum:

When proving things using Big-$O$ notation where you are allowed to use limits I recommend the following table:

table

Where $f(n) \in O(g(n))$ should actually be a Limit Superior. I think that $f(n) \in \Omega(g(n))$ should be a Limit Inferior, but $\Omega$ notation is rarer and I haven't encountered it.

$\endgroup$
3
  • $\begingroup$ $f \in \Theta(g)$ is not the same as $\lim_{x \to \infty} f(x)/g(x) \in \mathbb R_{>0}$. $\endgroup$ Commented Feb 22, 2017 at 9:58
  • $\begingroup$ @AntonioVargas technically we need to make sure the limit superior and limit inferior exist and are less than infinity and greater than zero respectively. For well behaved functions we can simply make sure the limit is in $\mathbb{R}_{>0}$. I explain this in my post. Once both of these conditions are met, the limit definition matches the classic definition $\endgroup$ Commented Feb 22, 2017 at 14:28
  • $\begingroup$ Huh. Negative votes on one of the longest answers I've written, and by far the most detailed. Reputation works so strangely on this site $\endgroup$ Commented Feb 23, 2017 at 3:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .