Analysis of Recursive algorithms

• Read 2.4, pages 70-76
  • Study the algorithm in Example 1, for computing the factorial function.
    • What do we consider as the problem’s size? Why is this not entirely correct?
    • What do we consider as the algorithm’s basic operation?
    • Explain the recurrence relation, at the top of page 71, for the number \(M(n)\) of multiplications needed to compute the \(n\)-th fibonacci number.
    • What else do we need in addition to the recurrence relation, in order to compute \(M(n)\)? Where is that number coming from?
    • Why is \(M(0) = 0\)?
    • Use the method of backward substitutions to solve this recurrence relation.
  • What are the five steps followed in the plan to analyze the time efficiency of recursive algorithms? Where does it differ with the plan for non-recursive algorithms?
  • Study the Towers of Hanoi recursive algorithm in Example 2.
    • Explain the recurrence relation for the number \(M(n)\) of moves needed, described at the top of page 74.
    • Use the method of backward substitutions to solve this recurrence relation.
    • Look at the tree-based description at the bottom of page 75. How does that computation relate to the computation of \(M(n)\) you just did? Do they count the same things?
  • Study the “number of digits in binary representation” algorithm of example 3.
    • Explain why this algorithm would correctly compute the number of binary digits that the input number’s representation uses.
    • Explain why it is enough to consider the algorithm’s time efficiency in the case where \(n\) is a power of \(2\).
    • Explain the final formula for the time efficiency class of this algorithm.
  • Practice problems: 2.4.1, 2.4.3, 2.4.4, 2.4.9
  • Challenge: 2.4.13, 2.4.14