Time Complexity Analysis: A Quick Reference for Interviews

Every coding interview ends with "What is the time and space complexity?" Guessing signals weak fundamentals. This reference teaches you to analyze complexity systematically.

Common Complexities

O(1) -- Constant. Hash map lookups, array access by index, stack push/pop.

O(log n) -- Logarithmic. Problem size halved each step. Binary search, balanced BST operations.

O(n) -- Linear. Process each element once. Single-pass scans, hash map construction.

O(n log n) -- Linearithmic. Comparison-based sorting (merge sort, heap sort). If your solution sorts first, the floor is O(n log n).

O(n^2) -- Quadratic. Nested loops over input. Bubble sort, brute-force pair finding. Usually the naive solution you should optimize.

O(2^n) -- Exponential. Branching recursion without memoization. Fibonacci without caching, generating all subsets.

O(n!) -- Factorial. Generating all permutations. Backtracking with full exploration.

Analyzing Loops

Single loop over n elements: O(n). Nested loops both over n: O(n^2). Inner loop depends on outer (runs i times): still O(n^2) since 1+2+...+n = n(n+1)/2. Loop halving input: O(log n). Outer loop O(n) with inner O(log n): O(n log n).

Let's illustrate these patterns with concrete code examples.

Single Loop - O(n): A simple traversal to find a maximum value.

def find_max(arr):
    max_val = float('-inf')
    for num in arr:          # Single loop over n elements
        if num > max_val:
            max_val = num
    return max_val

Nested Loops - O(n²): A naive algorithm to find all pairs.

def find_all_pairs(arr):
    pairs = []
    n = len(arr)
    for i in range(n):          # Outer loop runs n times
        for j in range(i + 1, n): # Inner loop runs n-i-1 times
            pairs.append((arr[i], arr[j]))
    return pairs

Loop Halving Input - O(log n): Binary search is the classic example.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1   # Discard left half
        else:
            right = mid - 1  # Discard right half
    return -1

Analyzing Recursion

Recursion tree method. Draw the tree, sum work at all nodes. Fibonacci: ~2^n nodes, O(1) each = O(2^n). With memoization: n unique calls = O(n). Merge sort: log n levels, O(n) work per level = O(n log n).

Let's examine the naive Fibonacci recursion (O(2ⁿ)) versus the memoized version (O(n)).

# Naive Fibonacci - O(2ⁿ) time, O(n) space (call stack depth)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Memoized Fibonacci - O(n) time, O(n) space
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Master theorem (simplified). For T(n) = a * T(n/b) + O(n^d):

• d > log_b(a): O(n^d) -- top level dominates
• d == log_b(a): O(n^d * log n) -- work evenly distributed
• d < log_b(a): O(n^(log_b(a))) -- leaves dominate

Merge sort: a=2, b=2, d=1. d == log_2(2), so O(n log n). Binary search: a=1, b=2, d=0, so O(log n).

Let's see how the Master Theorem applies to Merge Sort.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # T(n/2)
    right = merge_sort(arr[mid:])  # T(n/2)
    return merge(left, right)      # O(n) work to merge

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Here, the recurrence is T(n) = 2T(n/2) + O(n). So a = 2, b = 2, d = 1. Since log_b(a) = log_2(2) = 1, and d == log_b(a), we are in case 2, resulting in O(n^d * log n) = O(n log n).

Space Complexity

Call stack. Recursive solutions use O(depth) space. Balanced tree: O(log n). Linear recursion: O(n).

Auxiliary structures. Hash map for frequency: O(n) worst case. Fixed array of 26 chars: O(1).

Sorting space. Merge sort: O(n). Quick sort: O(log n) average. Heap sort: O(1).

Consider a function that counts character frequencies. Its space complexity depends on the auxiliary data structure used.

# O(n) space - using a hash map that can grow with input size
def count_freq_hash(s):
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    return freq

# O(1) space - using a fixed-size array for lowercase letters
def count_freq_array(s):
    freq = [0] * 26  # Fixed size, independent of input length
    for ch in s:
        if 'a' <= ch <= 'z':
            idx = ord(ch) - ord('a')
            freq[idx] += 1
    return freq

Data Structure Costs

Understanding these costs in practice is crucial. Let's look at examples of operations with different complexities across data structures.

Array Insert vs. Heap Insert: Inserting into an unsorted array at the end is O(1), but inserting into a sorted position is O(n). Inserting into a heap is always O(log n).

# Array: Insert at end is O(1), but insert in sorted order is O(n)
def insert_sorted_array(arr, val):
    i = len(arr) - 1
    arr.append(val)  # Amortized O(1)
    # Shift elements to maintain sorted order: O(n) worst case
    while i >= 0 and arr[i] > val:
        arr[i + 1] = arr[i]
        i -= 1
    arr[i + 1] = val

# Heap: Insert is O(log n)
import heapq
def insert_into_heap(heap, val):
    heapq.heappush(heap, val)  # O(log n)

Hash Map Search vs. Array Search: Searching for an element in an unsorted array is O(n), while a hash map provides average O(1) lookup.

# Array search: O(n)
def search_array(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Hash map search: O(1) average
def search_hash_map(hash_map, key):
    return hash_map.get(key, -1)  # O(1) average

Amortized Analysis

Dynamic array append is O(1) amortized -- the expensive O(n) resize happens infrequently. Over n appends, total work is O(n). Same principle applies to hash map inserts and union-find operations.

Let's simulate the amortized cost of appending to a dynamic array. While an individual append might trigger an expensive resize, the average cost over many operations is constant.

class DynamicArray:
    def __init__(self, capacity=2):
        self.capacity = capacity
        self.size = 0
        self.arr = [None] * capacity

    def append(self, val):
        if self.size == self.capacity:
            self._resize()  # O(n) operation
        self.arr[self.size] = val
        self.size += 1

    def _resize(self):
        print(f"Resizing from {self.capacity} to {self.capacity * 2}")
        new_arr = [None] * (self.capacity * 2)
        for i in range(self.size):
            new_arr[i] = self.arr[i]  # Copy old elements: O(n)
        self.arr = new_arr
        self.capacity *= 2

# Amortized analysis: Over n appends, total work is O(n), so average O(1) per append
def demonstrate_amortized():
    da = DynamicArray()
    for i in range(10):
        da.append(i)

The key insight is that resizes happen at powers of 2 (after 2, 4, 8, 16... elements). The total copy work for n inserts is proportional to n (specifically, less than 2n), making the average cost per insert constant.

Communicating in Interviews

State both time and space. Be specific: "O(n log n) due to sorting, O(n) space for the hash map." Walk through the reasoning rather than guessing. Count loops, identify the dominant term, state it. Interviewers prefer correct reasoning at a slower pace over a fast wrong answer.

Let's analyze a complete example: Finding two numbers in an array that sum to a target.

Naive Solution (O(n²) time, O(1) space): Check all pairs.

Optimized Solution (O(n) time, O(n) space): Use a hash map for constant-time lookups.

def two_sum_naive(nums, target):
    # O(n²) time, O(1) space
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum_optimized(nums, target):
    # O(n) time, O(n) space
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:          # O(1) average lookup
            return [seen[complement], i]
        seen[num] = i
    return []

When communicating complexity for the optimized solution, you should say: "This solution runs in O(n) time because we make a single pass through the array, and each hash map lookup and insert is O(1) on average. The space complexity is O(n) in the worst case to store up to n elements in the hash map."

Remember to:

1. Identify the input size n (usually the length of the primary data structure).
2. Count the dominant operations (loops, recursive calls).
3. Consider auxiliary data structures for space complexity.
4. State any assumptions (e.g., "assuming a good hash function").
5. Mention trade-offs when comparing approaches.

By systematically applying these principles and practicing with concrete examples, you'll develop the intuition to quickly and accurately analyze complexity in any interview scenario.