Big-O and Why It Matters

Time and space complexity

Big-O describes how work grows with input size: O(1) constant, O(log n) binary search, O(n) one pass, O(n log n) sorting, O(n²) nested loops, O(2ⁿ) subsets. Constraints hint at the target: n up to 10⁵ usually needs O(n log n) or better, while n up to 20 allows exponential search. Trading space for time (a hash map, a memo table) is the most common optimisation.

Counting steps for Two Sum, run

I ran this with Python 3.12.3 (standard library only). In the worst case (answer at the end) the brute force checks n(n-1)/2 pairs, which reaches 499,500 for n = 1,000, while the hash map needs only n steps.

# Two Sum: brute force O(n^2) vs hash map O(n), counting basic steps
def two_sum_brute(nums, target):
    steps = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            steps += 1
            if nums[i] + nums[j] == target:
                return [i, j], steps
    return None, steps

def two_sum_hash(nums, target):
    seen, steps = {}, 0
    for i, x in enumerate(nums):
        steps += 1
        if target - x in seen:
            return [seen[target - x], i], steps
        seen[x] = i
    return None, steps

for n in (10, 100, 1000):
    nums = list(range(n))
    target = (n - 2) + (n - 1)          # answer is the last pair: worst case
    print(f"n={n:5}  brute steps={two_sum_brute(nums, target)[1]:>7,}  hash steps={two_sum_hash(nums, target)[1]:>5,}")
print(two_sum_hash([2, 7, 11, 15], 9)[0])

Output:

n=   10  brute steps=     45  hash steps=   10
n=  100  brute steps=  4,950  hash steps=  100
n= 1000  brute steps=499,500  hash steps=1,000
[0, 1]

Finding a friend at a party

Asking every pair of guests whether they are your friend and their partner is O(n²); keeping a guest list you can check instantly is O(n).

Quick check: With n up to 100,000, which complexity is usually acceptable?

• O(n log n)
• O(n²)
• O(2ⁿ)
• O(n!)