College of Computer & Information Science Fall 2006 Northeastern University Handout 4 CSU690: Algorithms and Data 19 September 2006

Mathematical Notation, Definitions, and Review

Inequalities f(n) is “monotonically increasing”: m ≤ n ⇒ f(m) ≤ f(n) f(n) is “monotonically decreasing”: m ≤ n ⇒ f(m) ≥ f(n) f(n) is “strictly increasing”: m ≤ n ⇒ f(m) < f(n) f(n) is “strictly decreasing”: m ≤ n ⇒ f(m) > f(n) ⌊x⌋ = max{ y : y ≤ x, y an integer } (“floor”) ⌈x⌉ = min{ y : y ≥ x, y an integer } (“ceiling”) Fact: x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1 Fact: ⌈⌈n/a⌉/b⌉ = ⌈n/ab⌉ and ⌊⌊n/a⌋/b⌋ = ⌊n/ab⌋ f(n) is “polynomially bounded” if f(n) = O(n^{k}) (for some constant k) = n^{O(1)} Exponentials ∀a ≠ 0, ∀m, m,

a^{0} = 1,

a^{1} = a,
a^{−1} = 1/a,
(a^{m})^{n} = a^{mn}, and
a^{m}a^{n} = a^{m+n}.

e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + ⋯ = ∑_{i=0}^{∞} \frac{x^{i}}{i!} (Taylor’s series)

1 + x ≤ e^{x} ≤ 1 + x + x^{2} (for |x| < 1)

lim_{n→∞}(1 + \frac{x}{n})^{n} = e^{x}

Logarithms Definition: log_{b} a = c if and only if a = b^{c} ∀a, b, c > 0, ∀n,

a = b^{log_{b} a},

log_{c}(ab) = log_{c} a + log_{c} b,
log_{b} a^{n} = n log_{b} a,
log_{b} a = \frac{log_{c} a}{log_{c} b},
log_{b}(1/a) = log_{b} a^{−1} = − log_{b} a,
log_{b} a = \frac{log_{a} a}{log_{a} b} = \frac{1}{log_{a} b}, and
a^{log_{b} n} = (b^{log_{b} a})^{log_{b} n} = b^{log_{b} a log_{b} n} = n^{log_{b} a}.

lg n = log_{2} n (binary logarithm) ln n = log_{e} n (natural logarithm) lg^{k} n = (lg n)^{k} lg lg n = lg(lg n) lg n + k = (lg n) + k ln(1 + x) = x − \frac{x^{2}}{2} + \frac{x^{3}}{3} − \frac{x^{4}}{4} + \frac{x^{5}}{5} − ⋯, |x| < 1 (Taylor’s series) \frac{x}{1+x} ≤ ln(1 + x) ≤ x, x > −1 f(n) is “polylogarithmically bounded” if f(n) = O(log^{k} n) (for some constant k) = log^{O(1)} n Factorial n! = 1 if n = 0, and n · (n − 1)! if n > 0 Alternatively, n! = 1 · 2 · 3 · · · · · n n! = \sqrt{2πn}(\frac{n}{e})^{n}(1 + Θ(\frac{1}{n})) (Stirling’s approximation) Binomial Coefficients \binom{n}{k} = \frac{n!}{k!(n−k)!} \binom{n}{k} = \binom{n}{n−k}

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k}

2^{n} = ∑_{k=0}^{n} \binom{n}{k}

\binom{n}{k} ≥ (\frac{n}{k})^{k} \binom{n}{k} ≤ \frac{n^{k}}{k!} ≤ (\frac{en}{k})^{k} (Stirling’s formula)

Summations A series is a sequence of partial sums of a summation, parametrized by the limit of summation. ∑_{k=1}^{n} a_{k} = a_{1} + a_{2} + ⋯ + a_{n} (finite series)

∑_{k=1}^{∞} a_{k} ≡ a_{1} + a_{2} + ⋯ = lim_{n→∞} ∑_{k=1}^{n} a_{k} (infinite series)

An infinite series is convergent if the limit exists. Otherwise the series is divergent. Linearity If a series is finite or convergent (for n replaced by ∞), then

∑_{k=1}^{n}(ca_{k} + b_{k}) = c ∑_{k=1}^{n} a_{k} + ∑_{k=1}^{n} b_{k}

Also, ∑_{k=1}^{n} Θ(f(k)) = Θ( ∑_{k=1}^{n} f(k))

Arithmetic Series Definition: ∑_{k=1}^{n} k = 1 + 2 + 3 + ⋯ + n

∑_{k=1}^{n} k = \frac{1}{2}n(n + 1) = Θ(n^{2})

Geometric Series Definition: ∑_{k=0}^{n} x^{k} = 1 + x + x^{2} + ⋯ + x^{n}

∑_{k=0}^{n} x^{k} = \frac{x^{n+1}−1}{x−1} ∀x ≠ 1

∑_{k=0}^{∞} x^{k} = \frac{1}{1−x} ∀|x| < 1

Harmonic series

Definition: H_{n} = ∑_{k=1}^{n} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ⋯ + \frac{1}{n}

H_{n} = ln n + O(1) Asymptotic Notation O(g(n)) = { f(n) : ∃ constants n_{0}, c > 0 such that ∀n ≥ n_{0}, 0 ≤ f(n) ≤ cg(n) } Ω(g(n)) = { f(n) : ∃ constants n_{0}, c > 0 such that ∀n ≥ n_{0}, cg(n) ≤ f(n) } Θ(g(n)) = { f(n) : ∃ constants n_{0}, c_{1}, c_{2} > 0 such that ∀n ≥ n_{0}, 0 ≤ c_{1}g(n) ≤ f(n) ≤ c_{2}g(n) } Alternatively, Θ(g(n)) = O(g(n)) ∩ Ω(g(n))) o(g(n)) = { f(n) : ∀ constant c > 0, ∃ constant n_{0} such that ∀n ≥ n_{0}, 0 ≤ f(n) < cg(n) } ω(g(n)) = { f(n) : ∀ constant c > 0, ∃ constant n_{0} such that ∀n ≥ n_{0}, cg(n) < f(n) } f(n) = O(g(n)) means f(n) ∈ O(g(n)) O(f(n)) = O(g(n)) means O(f(n)) ⊆ O(g(n))

(and similarly for Ω, Θ, o, and ω) 4