Week 02b: Analysis of Algorithms
Analysis of Algorithms
Running Time
Empirical Analysis
Theoretical Analysis
Pseudocode
The Abstract RAM Model
Primitive Operations
Counting Primitive Operations
Estimating Running Times
Big-Oh
Big-Oh Notation
Big-Oh and Rate of Growth
Big-Oh Rules
Asymptotic Analysis of Algorithms
Example: Computing Prefix Averages
Example: Binary Search
Math Needed for Complexity Analysis
Relatives of Big-Oh
Complexity Classes
Generate and Test Algorithms
Generate and Test
Example: Subset Sum
Summary
Produced: 2 Dec 2018