5
$\begingroup$

So here's an excerpt from Foundations of Computer Science by Alfred Aho and Jeffrey Ullman[1]. I've also found basically the same material in a few other places, and also in my discrete math textbook, but this is clearest one I've seen:

Example 3.2. Suppose we have a program whose running time is $T(0) = 1$, $T(1) = 4$, $T(2) = 9$, and in general $T(n) = (n + 1)^2$. We can say that $T(n)$ is $O(n^2)$, or that $T(n)$ is quadratic, because we can choose witnesses $n_{0} = 1$ and $c = 4$. We then need to prove that $(n + 1)^2 \leq 4n^2$, provided $n \leq 1$. In proof, expand $(n + 1)^2$ as $n^2 + 2n + 1$. As long as $n \leq 1$, we know that $n \leq n^2$ and $1 \leq n^2$. Thus $n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 = 4n^2$.

Even so, I get lost where it says:

$$ n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 $$

I get that it's true, but it seems arbitrary. How/why did the expression get modified on the right side of the $\leq$ like it did? Couldn't they also have done this?

$$ n^2 + 2n + 1 \leq 4n^2 + 0 + 0 $$

Specifically, what rule did they apply to transform the expression $n^2 + 2n + 1$ into $n^2 + 2n^2 + n^2$?


  1. http://infolab.stanford.edu/~ullman/focs.html
$\endgroup$
4
$\begingroup$

They want to end up with ​ constant * n2 ​ on the very-right.
They applied "make each term a constant times n2".

$\endgroup$
  • $\begingroup$ Why did they do it in that particular way? Couldn't they just as easily have done $n^2 + 2n + 1 \leq 4n^2 + 0n^2 + 0n^2$ ? $\endgroup$ – greim Apr 10 '16 at 20:41
  • $\begingroup$ They'd have to show that inequality, which would involve what they actually did. ​ ​ $\endgroup$ – user12859 Apr 10 '16 at 21:19
4
$\begingroup$

Claim:

$$ n^2 + 2n + 1 \le 4n^2$$

we know it is true, but we still need to prove it.

One option, is to shift sides, getting $3n^2-2n+1 \ge 0$, and solving this equation shows it holds for any $n\ge 1$. But this is cumbersome.

What else can we do? We can take a crude bound for each term. For instance, $n^2 \le n^2$, $2n \le 2n^2$, and $1\le n^2$ hold for any $n\ge1$! Therefore, it is valid to say that $$n^2 + 2n + 1 \le n^2 +2n^2 +n^2 \le 4n^2.$$ and it is quite intuitive and easy to see, even for the non-expert.

What's wrong with $n^2 + 2n + 1 \le 4n^2 + 0+0$?
Technically, nothing is wrong - this is a valid claim for any $n\ge 1$.
However intuitively this derivation is misleading: it suggests that we bound the three terms one by one, which "suggests" the incorrect derivation of $n^2 \le 4n^2$; $2n \le 0$; and $1\le 0$.

Bottom-line: since Aho-Ullman is meant for students, it tries to give simple explanations that any reader can easily verify in the most simple way, even if it is longer and less "direct".


(actually this is not a CS question, but math. Hmpf.).

$\endgroup$
  • $\begingroup$ Thanks for this answer. So they had to transform the expression $4n^2$ into an equivalent expression $n^2 + 2n^2 + n^2$ in order to have an explicit term-for-term comparison to $n^2 + 2n + 1$. $\endgroup$ – greim Apr 12 '16 at 5:39

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.