9780023606922, Chapter 2 4, Problem 28E

Prévia do material em texto

Chapter 2.4, Problem 28E Step-by-step solution Step 1 of 4 Recurrence relation for 2 +2 If If n n even odd n n # 1 We have to prove that is not non-decreasing, this can be done by the method of mathematical induction. Step 2 of 4 Basic Step: We have to check whether the statement is true for Therefore for n = the statement is true. Step 3 of 4 Inductive Step: Assume k is even and for all We have to check whether the statement is true for n=k+1 When odd. When k is even Therefore can be written as Thus, for all even Assume k is odd and for all k. We have to check whether the statement is true for n=k+1 as is even Thus, for all odd Therefore we can conclude that for all Hence it is proved. Step 4 of 4 Specified algorithm: exp2 (a,n) return a power = exp2(a,m) power = power X power if(n is even) return power else return power xa } Consider to be the number of multiplications involved in computing a"-