Data Structures & Big-O (CS 201) · Module 1 of 9
Asymptotic Analysis Foundations
The formal notation for describing how an algorithm scales, and how to read it off real code.
Formal Definitions: O, Ω, Θ
- Big-O (O) gives an asymptotic upper bound: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.
- Big-Omega (Ω) gives an asymptotic lower bound (f(n) ≥ c·g(n)); Big-Theta (Θ) means both bounds hold simultaneously, giving a tight bound.
If an algorithm's runtime is Θ(n log n), what does that tell you compared to just knowing it's O(n log n)?
Solution. Θ(n log n) means n log n is both an upper AND lower bound — the algorithm's growth rate is exactly n log n, not just "at most" n log n; O(n log n) alone only guarantees it won't grow faster than that.
Common Growth Classes
- From fastest to slowest growing: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
- Constant and logarithmic algorithms scale extremely well; exponential and factorial algorithms become impractical even for modest input sizes.
Why does an O(2ⁿ) algorithm quickly become impractical, even for a computer that can do a billion operations per second?
Solution. Exponential growth means the number of operations roughly doubles with each additional input element; by n=60 or so, 2ⁿ already exceeds what even a very fast computer could compute in a reasonable amount of time.
Analyzing Loops & Recursion
- For loops: count how many times the loop body executes as a function of n; nested loops over the same input generally multiply, often giving n² or worse.
- For recursive algorithms, complexity depends on how many recursive calls are made, how the input shrinks each call, and how much work is done outside the recursive calls.
A function has two nested loops, both running from 0 to n. What is its time complexity?
Solution. O(n²) — the outer loop runs n times, and for each of those, the inner loop also runs n times, giving n × n = n² total iterations.
Best, Average, and Worst Case
- Best case describes the most favorable input, often unrealistic to rely on; worst case guarantees an upper bound regardless of input, which is usually the most important for practical guarantees.
- Average case requires assumptions about the input distribution and can be more realistic than worst case, but is often harder to analyze rigorously.
Why do computer scientists usually care most about worst-case complexity rather than best-case?
Solution. Worst-case complexity gives a guarantee that holds no matter what input is given, which is essential for reliability; best-case complexity only describes a possibly rare, favorable scenario and offers no guarantee for typical or adversarial inputs.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. What does Big-O notation describe?
2. What does Θ (Big-Theta) notation mean?