- Fast exponentiation base case?
- Recursion
- xn = … n/2 … if n even
- xn = … n-1 … if n odd
- Base case?
- n = 0 is trivial to compute, x0 = 1
- Recursion
- Recurrence for the maximum number of nodes in a binary tree as a
function of height
- Recurrence
- N(1) = 1
- N(h) = 1 + 2N(h-1), h > 1
- Guess based on summation analysis that N(h) = 2h - 1
- Recurrences of form T(n) = … a T(n-1) … tend to be exponential
- Recurrence
- Recurrence(s) for execution time of “fast” multiplication
multiply( x, y ) // x is a natural number if x = 0 return 0 else if x is even return multiply( x/2, 2*y ) else return multiply( x-1, y ) + y- T(0) = 1
- Best case (x = 2k for some k ≥ 0) / worst case
- Best case
- Recurrence (in terms of k)
- T(0) = 1
- T(k) = T(k-1) + 1, k > 0
- T(k) = k+1 from Tuesday result
- So T(x) = T(2k) = k+1 = log2x + 1 = Θ( log n )
- Or in terms of x…
- T(1) = 1
- T(x) = 1 + T(x/2), x > 1
- Recurrence (in terms of k)
- T(n) = … T( n/a ) … tends to have logarithmic closed form
- Find closed form for book’s T(n) = 2 T(n/2) + n; T(1) = 1
- Substitution to try to guess closed form:
- T(n) = 2 T(n/2) + n
- = 2( 2T(n/4) + n/2 ) + n = 4T(n/4) + 2n
- = 4( 2T(n/8) + n/4 ) + 2n = 8 T(n/8) + 3n = 23 T(n/23) + 3n
- T(n) = n log2n + n?
- Proof for powers of 2
- Base case, n = 1, checks out
- Assume T(k) = k log2k + k
- Show T(2k) = 2k log2(2k) + 2k = 2k( log22
+ log2k) + 2k
- T(k) = k log2k + k
- 2 T(k) = 2k log2k + 2k
- 2 T(k) + 2k = 2k log2k + 2k + 2k
- T(2k) = 2k log2k + 2k + 2k = 2k( log2k + 1) + 2k
- = 2k( log2k + log22) + 2k
- Substitution to try to guess closed form:
- Master method for solving (some) recurrences
- Master method ≈ “use the Master Theorem”
- Read
- Theorem 4.1 (statement of Master Theorem), page 94
- Section 4.6 (the proof)