Algorithm
Learn how an algorithm's running time and memory grow with input size using Big-O notation, and how to confirm the analysis by measuring.
Complexity analysis describes how the time and memory an algorithm needs grow as its input gets larger. Instead of seconds, which depend on hardware and language, it counts basic operations as a function of the input size n and keeps only the dominant term. The result is written in asymptotic notation: Big-O for an upper bound, Big-Omega for a lower bound and Big-Theta for a tight bound.
It matters because, once data grows, the gap between growth rates outweighs any constant factor. An O(n²) routine that is fine for a thousand items can take hours on a million, while an O(n log n) one finishes in seconds. Complexity is how you choose data structures, read the input limits of a coding problem, spot hidden costs in code review and estimate whether a system will scale.
Start by counting operations in simple loops and learning the common classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and O(n!). Then move on to best, average and worst cases, amortized analysis, space complexity and solving recurrences with the master theorem. Throughout, check your reasoning with a doubling experiment: time the code at n and 2n and compare the ratio.
O, Ω and Θ give upper, lower and tight bounds on growth, ignoring constant factors and lower-order terms.
Add the costs of sequential code, multiply for nested loops, and expect a logarithm when each step halves the problem.
Averages cost over a whole sequence of operations, which is why appending to a dynamic array is O(1) even though it occasionally copies everything.
Auxiliary memory and recursion depth count too, and the master theorem solves divide-and-conquer recurrences.
The script solves one problem two ways: checking every pair, and a single pass that remembers seen values in a dictionary. Timing both with timeit at n = 500, 1,000 and 2,000 shows that each doubling makes the quadratic version about four times slower and the linear one about twice as slow.
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pySix chapters that take you from installation to the core ideas of Complexity analysis.
Ask questions, share experience and trade opinions about Complexity analysis.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.