Algorithm Analysis and Design

Characterizing Algorithms

Measures of Complexity: Big Oh

   Big Oh

Example: Trivial Algorithm

Example: Bubble Sort
(not a very good description of the algorithm)

Example:
Binary Search

Example: Multiple-class Mean Value Analysis
(don’t worry about MVA details)

   Average Case Analysis

   Summary