Time and Space Complexity

Complexity describes how the running time (or memory) of an algorithm grows with the input size n. We use Big-O notation to describe the upper bound while ignoring constants.

Common growth rates​

Counting operations​

def has_pair_with_sum(nums, target):
    seen = set()               # O(n) extra space
    for x in nums:             # n iterations
        if target - x in seen: # O(1) average lookup
            return True
        seen.add(x)
    return False               # Time O(n), Space O(n)

Rules of thumb​

1. Drop constants: O(2n) is O(n).
2. Keep the dominant term: O(n² + n) is O(n²).
3. Sequential steps add; nested steps multiply.
4. Recursion: count the number of calls times the work per call.

Best, average and worst case​

Quick sort is O(n log n) on average but O(n²) in the worst case (already sorted input with a poor pivot). Always say which case you mean.