9780023606922, Chapter 2, Problem 18E

Prévia do material em texto

Chapter 2, Problem 18E Step-by-step solution Step 1 of 3 Inductive proof of Main Recurrence theorem Consider T(n) satisfying: Where and a=b* Consider the expression T(n) log for all n We have to prove the given expression by the method of mathematical Step 2 of 3 Basic Step: To check whether the statement is Therefore for n=n₀ the above statement is true. Inductive Step: Assume Since, Where Therefore, from the inductive hypothesis: Step 3 of 3 Since, a=b* The inductive step has been completed. Therefore T(n) logn for all n≥1 and this implies Hence it is proved.