Class 24: Algorithm Analysis, Continued

Held Wednesday, October 4, 2000

Summary

Today we consider what makes Grinnell great, potentially as it relates to computer science.

Notes

• Are there any other questions on homework 3?
• In preparation for tomorrow's consultants visit, I thought we might consider
  • What makes Grinnell great?
  • What is the Grinnell community passionate about?
  • What can Grinnell do better than anyone?
• I was dealing with too much problematic email this morning, so I'm behind in having the outline ready. Blah.

Overview

• What makes Grinnell great.
• How to analyze iterative algorithms.

Computing Running Times of Iterative Algorithms

An attempt to summarize what we discussed yesterday.

• An assignment statement: Count 1 unit.
• A non-recursive function call: Count the cost of the function.
• A sequence of statements: Sum the costs of the statements.
• A conditional: Take the worst of the two cases (or the sum, if that's easier).
• A loop: Multiply the number of repetitions (or an upper bound on the number of repetitions) by the cost of the body.