1. Basic rules for upper bounds

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

• In a sum, or in a product of positive terms, you can replace smaller things with bigger things.
  • Examples.
    • n + 1 ≤ n + n = 2n [provided n ≥ 1].

    • n * 1 ≤ n * n = n² [again provided n ≥ 1].

    • ∑_{i = 1 to n} i log i ≤ ∑_{i = 1 to n} n log n = n² log n.

  • When to do this
    • When the bigger thing is simpler but not much bigger (especially if it will disappear into a big-O later).

      • n + 1.9117893 < n + 2.

      • n * 17 ln 2 < 12n.

    • When the bigger thing is dominated by some other term anyway.

      • n² + n ≤ n² + n² = 2n² = O(n²) [when n ≥ 1].

    • Hint: If the answer you get is too big, go back and look for an inequality with a lot of slop in it (e.g n < 2ⁿ).

• In the denominator of a fraction, you can replace bigger things with smaller things.
  • n / ln n ≤ n / 1 = n [when ln n ≥ 1].
• The general rule: replace smaller things with bigger things in the argument to an increasing function (see below), and bigger things with smaller things in the argument of a decreasing function.

  • (1.77689136 n)¹² < (2x)¹².

  • -(x+13) < -x. (Here the decreasing function is f(x) = -x.)

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

• Functions may be increasing only for certain ranges; for example, f(n) = n² is increasing for n > 0 but decreasing for n < 0.

• Increasing functions can be applied to both sides of an inequality without breaking it. If both sides of the first inequality are positive, then (x + ln x) > (y + 12/y) implies (x + ln x)² > (y + 12/y)².

• The inverse of an increasing function is also increasing: Since x² is increasing for x > 0, so is x^1/2 (i.e. sqrt(x)).

• The composition of increasing functions is increasing: Since x² and ln x are both increasing functions for x > 0, ln² x is increasing for x > 0.

• Examples of increasing functions (for sufficiently large x):

  • x^a for any constant a > 0.

  • log x.

  • a^x for any constant a > 1.

  • Another way to say that a > b implies a + c > b + c is to say that addition is an increasing function (in either argument). Similarly, multiplication is an increasing function if both arguments are positive.

  • a/x is a decreasing function of x for positive a and x.

  • ⌊x⌋ and ⌈x⌉ are both nondecreasing (but not increasing since ⌊3.14⌋ = ⌊3.78⌋ = 3).
• The derivative test: f(x) is

  • increasing	if f'(x) is positive (> 0)
    nondecreasing	if f'(x) is non-negative (≥ 0)
    nonincreasing	if f'(x) is non-positive (≤ 0)
    decreasing	if f'(x) is negative (< 0)

    This only works for functions that have derivatives (so not for ⌊x⌋). See HowToDifferentiate for help on taking derivatives.

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 < 2ⁿ 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 < 2⁰ = 1. Now we want to show that the gap between n and 2ⁿ doesn't go down for larger n---in particular, that 2ⁿ - n is a nondecreasing function. We can do this by taking derivatives:

• (d/dn) 2ⁿ - n = 2ⁿ ln 2 - 1.

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

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

• (d/dn) 2ⁿ ln 2 - 1 = 2ⁿ ln² 2 - 0 > 0 [since 2ⁿ > 0 for all n and ln² 2 (whatever its actual value is) is positive].

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 x² + (n-x)² that only uses n. To do this we need to find the smallest value that x² + (n-x)² 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 x² + (n-x)² 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)² + (n/2)² = n²/2 ≤ x² + (n-x)².

More general problems can be solved using LagrangeMultipliers.

---

CategoryAlgorithmNotes CategoryMathNotes