# 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

^{2}[again provided n ≥ 1].∑

_{i = 1 to n}i log i ≤ ∑_{i = 1 to n}n log n = n^{2}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

^{2}+ n ≤ n^{2}+ n^{2}= 2n^{2}= O(n^{2}) [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

^{n}).

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

- Examples.
- 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)

^{12}< (2x)^{12}.-(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**.^{1}

Functions may be increasing only for certain ranges; for example, f(n) = n

^{2}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)

^{2}> (y + 12/y)^{2}.The inverse of an increasing function is also increasing: Since x

^{2}is increasing for x > 0, so is x^{1/2}(i.e. sqrt(x)).The composition of increasing functions is increasing: Since x

^{2}and ln x are both increasing functions for x > 0, ln^{2}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^{n} 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^{0} = 1. Now we want to show that the gap between n and 2^{n} doesn't go down for larger n---in particular, that 2^{n} - n is a nondecreasing function. We can do this by taking derivatives:

(d/dn) 2

^{n}- n = 2^{n}ln 2 - 1.

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

Well, at n = 0, 2^{n} ln 2 - 1 = 2 ln 2 - 1 = 0.386294... > 0. To prove that it never drops below 0, we'll show that 2^{n} ln 2 - 1 is nondecreasing. We could do this using the fact that 2^{n} 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

^{n}ln 2 - 1 = 2^{n}ln^{2}2 - 0 > 0 [since 2^{n}> 0 for all n and ln^{2}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^{2} + (n-x)^{2} that only uses n. To do this we need to find the smallest value that x^{2} + (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 x^{2} + (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} = n^{2}/2 ≤ x^{2} + (n-x)^{2}.

More general problems can be solved using LagrangeMultipliers.

CategoryAlgorithmNotes CategoryMathNotes

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