# Class 26: Analyzing Recursive Algorithms

Back to Project Discussion. On to More Recursive Algorithms.

Held Monday, October 9, 2000

Summary

Today we finally consider how to analyze recursive algorithms.

Notes

• Homework 3 is due at 5pm today.
• Are there any final questions?
• I'll grade it, but not until break.
• How did Friday's class go?
• For Friday, I'd like to have you have working stubs for the utility classes. Email them to your fellow students.
• I should have the next exam ready on Friday.
• I probably won't give you a homework assignment on algorithm analysis; your test will serve that purpose.
• I'll (finally) take questions on Bailey at the start of class tomorrow.

Overview

• Analyzing the recursive smallest algorithm
• Recurrence relations
• Binary search

## Running Times of Recursive Algorithms

• While you know some techniques for computing the running times of iterative algorithms, you don't know about ways to compute the running times of recursive algorithms.
• The iterative technique doesn't work for recursive algorithms because the function call involves the function itself.
• It is possible to rephrase every recursive algorithm iteratively.
• However, it may be easier to directly analyze the running time of a recursive algorithm.
• We'll consider our recursive smallest algorithm first.
• We'll begin by investigating a few recursive algorithms, including binary search, exponentiation, and various forms of computing values in the Fibonacci sequence.
• Binary search: find something in a sorted collection
• Exponentiation: compute xn
• Fibonacci: determine the nth element of the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, ...

## Recursive Smallest

• How much does it cost to ``split the array in half''?
• It depends on the implementation.
• How do we deal with the recursive call?

## Binary Search

• You learned binary search in 151 (or at least I think you did). We'll review it quickly and look at some analysis.
• To find something in a sorted collection:
• Identify the middle element of the collection
• If that's the thing you're looking for, you're done.
• If that thing is larger than what you're looking for, recurse on the subcollection of smaller elements.
• If that thing is smaller than what you're looking for, recurse on the subcollection of larger elements.
• What's the running time? How do you know?

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Monday, 9 October 2000

• Filled in the details.

Tuesday, 10 October 2000

• Removed uncovered details (now in the next outline).

Back to Project Discussion. On to More Recursive Algorithms.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.