Introduction
Once you can write a correct algorithm, the next question is how well it performs as the input grows. Algorithm analysis gives us a mathematical vocabulary, asymptotic notation, to describe running time and memory usage independent of any specific machine, programming language, or compiler. This lets you predict whether an algorithm will still be fast when the input size grows from a hundred items to a hundred million.
Cricket analogy: A coach judging a bowler's pace doesn't just watch one over on a flat Chepauk pitch; asymptotic notation is like rating bowling economy across any ground, so you can predict performance whether facing 6 balls or 600.
Key Concepts
Big-O notation, written O(f(n)), describes an upper bound on an algorithm's growth rate, the worst case. Big-Omega, written Omega(f(n)), describes a lower bound, the best case. Big-Theta, written Theta(f(n)), describes a tight bound where the upper and lower bounds match, giving the typical or exact growth rate. Common complexity classes, from fastest to slowest growing, include O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, O(2^n) exponential, and O(n!) factorial. When analyzing code, we count the dominant operations: loops that run n times contribute O(n), nested loops over the same input contribute O(n^2), and dividing the problem in half each step contributes O(log n). Space complexity follows the same notation but counts extra memory used, not counting the input itself.
Cricket analogy: Big-O is like the worst-case survival estimate against Mitchell Starc's yorkers, Big-Omega the best case against a part-time spinner, and Theta the typical outcome; a single over (O(1)) versus scanning the whole scorecard twice (O(n^2)) shows the range.
Example
def sum_of_pairs(items):
"""O(n^2) time: nested loop compares every pair."""
count = 0
n = len(items)
for i in range(n):
for j in range(i + 1, n):
if items[i] + items[j] == 10:
count += 1
return count
def sum_of_pairs_fast(items):
"""O(n) time, O(n) space: uses a set for O(1) average lookups."""
seen = set()
count = 0
for value in items:
complement = 10 - value
if complement in seen:
count += 1
seen.add(value)
return count
data = [2, 8, 3, 7, 5, 5]
print(sum_of_pairs(data)) # 3
print(sum_of_pairs_fast(data)) # 3Analysis
sum_of_pairs uses two nested loops, so its running time grows as O(n^2): doubling the input roughly quadruples the work. sum_of_pairs_fast trades additional memory (an O(n) set) for a single pass through the data, achieving O(n) time. This is a classic time-space trade-off: by remembering what we have already seen, we avoid re-scanning the list for every element. On a list of 10,000 items, the quadratic version performs on the order of 100 million comparisons while the linear version performs on the order of 10,000, a difference that becomes decisive at scale even though both versions are correct.
Cricket analogy: Checking every pair of batsmen's partnership totals by comparing each against every other is like sum_of_pairs's O(n^2) approach; keeping a running tally of totals already seen, like sum_of_pairs_fast, lets a scorer flag a matching partnership in one pass through a 10,000-run career database.
Key Takeaways
- Big-O describes the worst-case upper bound on growth rate; Big-Omega the best-case lower bound; Big-Theta the tight bound.
- Common complexity classes ordered from fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!).
- Nested loops over the same input typically indicate O(n^2) or worse; halving the problem each step indicates O(log n).
- Time and space can often be traded off, as seen when a hash set converts an O(n^2) algorithm into an O(n) one at the cost of extra memory.
Practice what you learned
1. What does Big-O notation describe?
2. A function with two independent (not nested) loops, each iterating n times over the input, has what time complexity?
3. Which complexity class grows fastest for large n?
4. In the sum_of_pairs_fast example, what resource is spent to reduce the time complexity from O(n^2) to O(n)?
Was this page helpful?
You May Also Like
Introduction to Algorithms
What an algorithm is, why it matters, and how to reason about correctness and efficiency before writing code.
The Master Theorem
Apply the Master Theorem's three cases to quickly solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).
Algorithm Complexity Cheat Sheet
A reference summary of time and space complexities for the major algorithms covered in this course.