Big-O and Analysis

Big-O describes growth rate as input size n increases.

Why It Matters

• Helps compare solutions independent of hardware.
• Predicts behavior on large inputs.
• Guides data structure choices.

Fast Complexity Estimation Rules

1. Keep only the dominant term (n^2 + n -> n^2).
2. Drop constants (5n -> n).
3. Sequential blocks add (O(a + b)).
4. Nested loops multiply (O(a * b)).

Examples

def sum_all(nums):
    total = 0
    for x in nums:
        total += x
    return total

Time: O(n) Space: O(1)

def all_pairs(nums):
    result = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            result.append((nums[i], nums[j]))
    return result

Time: O(n^2) Space: O(n^2) due to output size.

Amortized Analysis

Some operations are occasionally expensive but cheap on average.

• Dynamic array append: occasional resize O(n), average O(1) amortized.

Quick Pattern Map

Practice

1. Analyze complexity of finding max value in a list.
2. Analyze nested loops where inner loop runs k times only.
3. Compare linear search vs binary search complexity.