Chapter 4 Answers

Recurrence Relation Tutorial

Question - Is T(1) necessary? Yes when ën/2û = 1.

Question - Is T(1) necessary? Yes when én/2ù = 1.

Question

Inductive proofs on the recurrence: T(n) = T(n-1) + 1

Typically assume the case for parameter n that generates a sequence term for recurrence T(n) and prove T(n+1)=T((n+1)-1)+1.

For above recurrence: T(n) = T(ën/4û) + n

• What parameter value generates the next sequence term following T(n)?  T(n+1) = T(ë(n+1)/4û) + (n+1)

SUBSTITUTION METHOD

Question - Is this an exact solution for T(n)? No. But holds for definition of O(n lg n).