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
Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2016 at 20:41
  • $\begingroup$ They'd have to show that inequality, which would involve what they actually did. ​ ​ $\endgroup$
    – user12859
    Apr 10, 2016 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.).

Improve this answer
$\endgroup$
1
  • $\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, 2016 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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