Week 2: Analysis of Algorithms
Week 2
Nerds You Should Know
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 Analysis: Arrays vs. Linked Lists
Static/Dynamic Sequences
Self-referential Structures
Iteration over Linked Lists
Modifying a Linked List
Comparison Array vs. Linked List
Complexity Classes
Complexity Classes
Generate and Test
Example: Subset Sum
Summary
Produced: 28 May 2025
![[index]](icon/up.gif){kind=icon}