[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Basic rules for upper bounds

Here we want to show that (ugly expression) is less than or equal to (clean expression).

For lower bounds, where we want to prove (ugly expression) is greater than or equal to (clean expression), apply the same rules in reverse.

2. Monotone functions

A function f is increasing if x > y implies f(x) > f(y). It is decreasing if x > y implies f(x) < f(y). Some other terms are nondecreasing (x > y implies f(x) ≥ f(y)) and nonincreasing (x > y implies f(x) ≤ f(y)). Functions with any of these properties are called monotone or monotonic.1

Most functions encountered in AlgorithmAnalysis are increasing, or at least nondecreasing. Some functions are neither (f(x) = x mod 3).

3. The derivative trick

Suppose we want to prove n < 2n for sufficiently large n. None of the rules given above apply to this case. So how do we do it?

First let's find some n for which it is true. With some guesswork we can plug in n = 0 and observe that 0 < 20 = 1. Now we want to show that the gap between n and 2n doesn't go down for larger n---in particular, that 2n - n is a nondecreasing function. We can do this by taking derivatives:

and now we need to show that 2n ln 2 - 1 ≥ 0 for n ≥ 0. How?

Well, at n = 0, 2n ln 2 - 1 = 2 ln 2 - 1 = 0.386294... > 0. To prove that it never drops below 0, we'll show that 2n ln 2 - 1 is nondecreasing. We could do this using the fact that 2n and ln 2 are both positive and nondecreasing, so their product is also nondecreasing, or we could apply the derivative trick again:

The general pattern: To show f(x) < g(x) for all x > c, first show f(c) < g(c); then show that g(x) - f(x) is nondecreasing, either by using the rules for increasing functions or by showing (d/dx) (g(x) - f(x)) ≥ 0.

4. Finding extrema

This is useful when we have an inequality with some unbound variables in it. For example, suppose we want to compute an lower bound on x2 + (n-x)2 that only uses n. To do this we need to find the smallest value that x2 + (n-x)2 can take as we vary x. From calculus you may recall that the derivative of a function is 0 at a minimum or maximum, and that a positive second derivative indicates a minimum and a negative second derivative indicates a minimum. Taking the derivative of x2 + (n-x)2 gives 2x - 2(n-x); setting this to zero and solving for x gives x = n/2. We can test that this is a minimum and not a maximum by computing the second derivative 2+2 = 4 > 0. Since it is the only value of x for which the first derivative is zero, we can go still further and assert that it is a global minimum over all values of x.

Since we know that the minimum occurs at x = n/2, we can simply plug it in and get (n/2)2 + (n/2)2 = n2/2 ≤ x2 + (n-x)2.

More general problems can be solved using LagrangeMultipliers.

CategoryAlgorithmNotes CategoryMathNotes

  1. Confusing issue: sometimes monotone is used specifically to mean nondecreasing. (1)

2014-06-17 11:58