# Class 35: Algorithm Analysis (3)

Back to Algorithm Analysis (2). On to Dynamic Programming (1).

Held: Wednesday, April 5, 2006

Summary: Today we conclude our initial explorations of algorithm analysis with some experiments that explore our hypotheses.

Related Pages:

Notes:

• Readings and homework for Friday tbd.
• EC for cool scientific visualization talk today at 4:30.

Overview:

• Review.
• Lab.

## Review

• f(n) is in O(g(n)) iff
• there exists a number n0
• there exists a number d > 0
• for all but finitely many n > n0, abs(f(n)) <= abs(d*g(n))
• This notation provides a convenient mechanism for talking about running time without worrying about too many potentially useless details.
• We determine the asymptotic running time of an algorithm by "counting steps" for the worst case
• Sequence of operations: Add 'em up
• Assignment: 1
• Method call: Cost of that method
• Conditional: Worst cost of two branches
• Loop: Number of repetitions times cost of body

## Lab

• Do the lab.
• Be prepared to reflect in the last five or ten minutes.

Back to Algorithm Analysis (2). On to Dynamic Programming (1).

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:46 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.35.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu