Prévia do material em texto
Chapter 2, Problem 20E Step-by-step solution Step 1 of 4 Inductive proof of Main Recurrence theorem Consider T(n) Where and a>b* Consider the expression b* Therefore, The inductive step has been completed. Therefore for all n 1 and this implies that Hence it is proved.