Time & Space Complexity

Concept

Big-O describes how the running time or memory of an algorithm grows as the input size n grows. We drop constants and keep the fastest-growing term: 3n² + 5n + 2 becomes O(n²).

Common classes from fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2ⁿ) exponential.

Space complexity counts extra memory used, including recursion stack frames.

Complexity

Code (Python)

def has_pair_with_sum(nums, target):
    # O(n) time, O(n) space using a set
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

# Brute force would be O(n^2):
# for i in range(n): for j in range(i+1, n): ...

Remember

• Count loops: nested loops usually multiply.
• Halving the input each step gives log n.
• Trade space for time with hash sets / maps.