Lecture Overview L12−P. 1

Finding Summation Formulas Double Sums Computing Products: Estimating n! Asymptotic Notation Finding Summation Formulas L12−P. 2 What is the source of the simple formula? ∑_{i=1}^{n} i = \frac{n(n+1)}{2} and the source of:

∑_{i=1}^{n} i^{2} = \frac{(2n + 1)(n + 1)n}{6}
= \frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6}
∼ \frac{n^{3}}{3}

Integral method:

∫_{0}^{n} x^{2} dx ≤ ∑_{i=1}^{n} i^{2} ≤ ∫_{0}^{n}(x + 1)^{2} dx

\frac{n^{3}}{3} ≤ ∑_{i=1}^{n} i^{2} ≤ \frac{(n + 1)^{3}}{3} − \frac{1}{3}

Finding Summation Formulas, Cont. L12−P. 3

So, ∑_{i=1}^{n} i^{2} ∼ \frac{n^{3}}{3}

To get exact formula try: ∑_{i=1}^{n} i^{2} = an^{3} + bn^{2} + cn + d

Then try to plug enough values:

n = 0 → 0 = d
n = 1 → 1 = a + b + c + d
n = 2 → 5 = 8a + 4b + 2c + d
n = 3 → 14 = 27a + 9b + 3c + d

The solution is: a = 1/3, b = 1/2, c = 1/6, d = 0.

Now we must prove that our guess n^{3}/3 + n^{2}/2 + n/6 is correct.

Double Sums L12−P. 4

Sums of sums, Evaluate the inner sum, replace with a closed form and the the outer sum. Exchanging the order of summation. ∑_{k=1}^{n} H_{k} = ∑_{k=1}^{n} ∑_{j=1}^{k} 1/j just to start: ∑_{k=1}^{n} H_{k} ≈ ∫_{k=1}^{n} ln n ≈ n ln n − n. the pairs (k, j) over which we are summing, form a triangle:

j 1 2 3 4 ⋯ n
k
1 1
2 1 1/2
3 1 1/2 1/3
4 1 1/2 1/3 1/4
⋯
n 1 1/2  ⋯  1/n

Double Sums, Cont. L12−P. 5 More convinient to sum the columns and then the row: ∑_{k=1}^{n} H_{k} = ∑_{k=1}^{n} ∑_{j=1}^{k} 1/j

Computing Products: Estimating n! L12−P. 6

= ∑_{j=1}^{n} ∑_{k=j}^{n} 1/j = ∑_{j=1}^{n} 1/j ∑_{k=j}^{n} 1 = ∑_{j=1}^{n} \frac{1}{j}(n − j + 1) = ∑_{j=1}^{n} \frac{n−j+1}{j} = ∑_{j=1}^{n} \frac{n+1}{j} − ∑_{j=1}^{n} \frac{j}{j} = (n + 1) ∑_{j=1}^{n} \frac{1}{j} − ∑_{j=1}^{n} 1 = (n + 1)H_{n} − n Most common product is factorial: n! = 1 · 2 · 3 … (n − 1) · n = ∏_{i=1}^{n} i Convert to sum by logarithm

ln n! = ln(1 · 2 · 3 … (n − 1) · n)
= ln 1 + ln 2 + ln 3 + … + ln(n − 1) + ln n
= ∑_{i=1}^{n} ln i

Use integral method, recall ∫ ln x dx = x ln x− x

∫_{1}^{n} ln x dx ≤ ∑_{i=1}^{n} ln i ≤ ∫_{0}^{n} ln(x + 1) dx
n ln(\frac{n}{e}) + 1 ≤ ∑_{i=1}^{n} ln i ≤ (n + 1) ln (\frac{n + 1}{e}) + 1
(\frac{n}{e})^{n} e ≤ n! ≤ (\frac{n + 1}{e})^{n+1} e

n! ≈ (\frac{n}{e})^{n}.

More careful calculation results in:

Fact 1 (Stirling’s Formula)

\sqrt{2πn} (\frac{n}{e})^{n} e^{1/(12n+1)} ≤ n! ≤ \sqrt{2πn} (\frac{n}{e})^{n} e^{1/12n}

Since e^{1/(12n+1)} and e^{1/12n} both approach 1 as n grows large.

Bounds are tight e.g., :

100! ≥ \sqrt{200π} (\frac{100}{e})^{100} e^{1/1201}
100! ≤ \sqrt{200π} (\frac{100}{e})^{100} e^{1/1200}

Asymptotic Notation L12−P. 9 f(n) ∼ g(n) means lim_{n→∞} \frac{f(n)}{g(n)} → 1.

H_{n} = ∑_{i=1}^{n} \frac{1}{i}
= ln n + γ + \frac{1}{2n} + \frac{1}{12n^{2}} + \frac{ϵ(n)}{120n^{4}}
∼ ln n

And, n! ∼ \sqrt{2πn}(\frac{n}{e})^{n}.

Asymptotic Notation L12−P. 10

5 symbols for asymptotic notation:

O – “Oh” or “Big Oh” o – “Little Oh” Θ – “Theta” ω – “Little Omega” Ω – “Omega”

Big Oh L12−P. 11

Most frequently used, upper bound on the growth of a function e.g., running time of an algorithm

Definition Given functions f, g : R ↦ R, we say that f(x) = O(g(x)) if there exists a constant c > 0 and an x_{0} such that for all x ≥ x_{0}, |f(x)| ≤ cg(x).

f(x) = O(g(x)) means that f grows no faster than g. f(x) = O(g(x)) means f(x) ≤ g(x), except that we’re willing to ignore a constant factor (c) and to allow exceptions for small x (i.e., x < x_{0}).

Big Oh, Cont. L12−P. 12

Can express the idea f(x) = O(g(x)) by: f(x) ≤ O(g(x)), f(x) is O(g(x)), f(x) ∈ O(g(x)), or f(x) “is on the order of” g(x). is x = O(x^{2})?

Theorem: If f(x) = x and g(x) = x^{2}, then f(x) = O(g(x)).

Proof: We must prove that there exists a constant c > 0 and an x_{0} such that for all x ≥ x_{0}, |x| ≤ cx^{2}. In particular, we can choose c = 1 and x_{0} = 1. Then for all x ≥ 1, |x| ≤ 1 · x^{2}.

x^{2} = O(x)? No — x^{2} grows faster than x asymptotically.

Theorem: x^{2} ≠ O(x)

The proof is by contradiction. Assume (aim contradiction) that x^{2} = O(x). Then there exists a constant c > 0 and an x_{0} such that for all x ≥ x_{0}, |x^{2}| ≤ cx. This implies that for all x ≥ x_{0}, x ≤ c. False for x ≥ max(c + 1, x_{0}).

x^{2} = O(100x) is false as well.

Theorem: 100x^{2} = O(x^{2}) Proof: Choose c = 100 and x_{0} = 1. Then for all x ≥ 1, |100x^{2}| ≤ 100x^{2}

Theorem: x^{2} + 100x + 10 = O(x^{2}) Proof: Choose c = 111 and x_{0} = 1. Then for all x ≥ 1, |x^{2} + 100x + 10| ≤ 111x^{2}.

Generalize the preceding theorem to an arbitrary quadratic polynomial.

Theorem: a_{1}x^{2} + a_{2}x + a_{3} = O(x^{2})

Proof: Choose c = |a_{1}|+|a_{2}|+|a_{3}| and x_{0} = 1. Then for all x ≥ 1, |a_{1}x^{2} + a_{2}x + a_{3}| ≤ (|a_{1}| + |a_{2}| + |a_{3}|)x^{2}.

Intuitively, exponential functions grow faster than polynomials, even very high degree polynomials.

Theorem: x^{10} = O(e^{x})

Proof: Choose c = 1 and x_{0} = e^{5}. It can be proven using calculus that 10 ln x ≤ x for all x ≥ e^{5}. Exponentiating gives that for all x ≥ e^{5}, we have e^{10 ln x} ≤ e^{x} or equivalently x^{10} ≤ e^{x}.

Example an algorithm that multiply n × n matrices runs in cubic time — T (n) = O(n^{3})

(ignoring terms related to machine specific).

If n doubles the runnimg time will increase by a factor of about 8 for large n.

Give indication for the scalability of an algorithm.

Big Oh, Exponential Fiasco L12−P. 16

is 4^{x} = O(2^{x})?

Theorem: 4^{x} ≠ O(2^{x})

Proof is by contradiction. Assume (aim contradiction) that 4^{x} = O(2^{x}). Then there exists a constant c > 0 and an x_{0} such that for all x ≥ x_{0}, |4^{x}| ≤ c2^{x}. This implies that for all x ≥ x_{0}, 2^{x} ≤ c. False for x ≥ max(ln(c + 1), x_{0}).

Constant Confusion L12−P. 17