Asymptotic Big-O Analysis & Space Complexity
Analyze O(1), O(log N), O(N), O(N log N), and O(N^2) asymptotic runtime and auxiliary memory growth curves.
Learning Objectives & Asymptotic Notation
### Learning Objectives
- Define Big-O ($mathcal{O}$), Big-Omega ($Omega$), and Big-Theta ($Theta$) asymptotic bounds.
- Classify algorithm runtime growth curves ($O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)$).
- Calculate auxiliary Space Complexity beyond input storage allocations.
- Eliminate lower-order non-dominant terms during asymptotic simplification.
---
### Big-O Notation Fundamentals
**Big-O Notation** measures how an algorithm's execution time or memory allocation grows relative to input size $N$ as $N$ approaches infinity.
