Report

Master Theorem Chen Dan Dong Feb. 19, 2013 Outline Review of asymptotic notations Understand the Master Theorem Prove the theorem Examples and applications Review of Asymptotic Notation Θ notation: asymptotic tight bound Θ(g(n)) = { f(n): there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}. O notation: asymptotic upper bound O(g(n)) = { f(n): there exist positive constants c, and n0 such that 0≤ f(n) ≤ cg(n) for all n ≥ n0}. Ω notation: asymptotic lower bound Ω(g(n)) = { f(n): there exist positive constants c, and n0 such that 0≤ cg(n) ≤ f(n) for all n ≥ n0}. Review of Asymptotic Notation (Con.) Asymptotic notation in equations Theorem: For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). Master Theorem Theorem: Let a ≥ 1 and b > 1 be constants, let f(n) be a function and let T(n) be defined on the nonnegative integers by recurrence T(n) = aT(n/b) + f(n), Then T(n) has the following asymptotic bounds. Case 1. If for some constant ϵ > 0, then Case 2. If then Case 3. If for some constant ϵ > 0, and if a f(n/b) ≤ c f(n) for some constant c < 1 and all sufficiently large n, then T(n) = Θ(f(n)). Proof of Master Theorem The proof consists of two parts The first part analyzes the recurrence under the simplifying assumption that T(n) is defined only on exact powers of b, for n = 1, b, b2, …. The second part extends the analysis to all positive integers n with handling floors and ceilings. Due to time limit, I will only show the proof for the first part for n as exact powers of b. Proof – Lemma 1 Lemma 1. Let a ≥ 1 and b > 1 be constants, let f(n) be a nonnegative function defined on exact powers of b. Define T(n) exact powers of b by the recurrence where j is a positive integer. Then Proof – Lemma 2 Lemma 2. Let a ≥ 1 and b > 1 be constants, let f(n) be a nonnegative function defined on exact powers of b. A function g(n) defined over exact power of b by has the following asymptotic bounds: Case 1. If for some constant ϵ > 0, then Case 2. If then Case 3. if a f(n/b) ≤ c f(n) for some constant c < 1 and all sufficiently large n, then g(n) = Θ(f(n)). Combining Lemma 1 and Lemma 2 Lemma 3. Let a ≥ 1 and b > 1 be constants, let f(n) be a nonnegative function defined on exact powers of b. Define T(n) exact powers of b by the recurrence Then T(n) has the following asymptotic bounds: Case 1. If for some constant ϵ > 0, then Case 2. If then Case 3. if for some constant ϵ > 0, and if a f(n/b) ≤ c f(n) for some constant c < 1 and all sufficiently large n, then g(n) = Θ(f(n)). If n is not exact powers of b… If n is not exact powers of b, then n/b is an not integer. We need to obtain a lower bound on T(n) = a T(⌈n/b⌉) + f(n) and an upper bound on T(n) = a T(⌊n/b⌋) + f(n). If intersted, check out here. Master Theorem Theorem: Let a ≥ 1 and b > 1 be constants, let f(n) be a function and let T(n) be defined on the nonnegative integers by recurrence T(n) = aT(n/b) + f(n), Then T(n) has the following asymptotic bounds. Case 1. If for some constant ϵ > 0, then Case 2. If then Case 3. If for some constant ϵ > 0, and if a f(n/b) ≤ c f(n) for some constant c < 1 and all sufficiently large n, then T(n) = Θ(f(n)). Some examples T(n) = 9 T(n/3) + n Case 1. T(n) = T(2n/3) +1 Case 2. T(n) = 2T(n/2) + n lgn Can’t apply Master Theorem. Binary Search Binary search finds the position of a specified value within a sorted array. Finding the recurrence relationship Applying Master Theorem. Case 2. T(n) = O(lg n).