Time and Space Complexity Interview Questions

Big O describes how running time or memory grows with input size n, ignoring constants and smaller terms: 3n² + 5n + 2 is O(n²). From fastest to slowest: O(1) hash lookup, O(log n) binary search, O(n) one pass, O(n log n) merge sort, O(n²) every pair, O(2^n) all subsets, O(n!) all permutations. Interviews usually mean the tight worst case.

Each pass halves n: 64, 32, 16, 8, 4, 2, 1 is 6 halvings, log₂(64). Any loop that divides the remaining work by a constant runs O(log n) times; a million items takes only about 20 steps.

The inner loop runs 4, 3, 2, then 1 times, so it prints 10. In general that is n(n + 1)/2 iterations, still O(n²): halving the work changes the constant, not the growth rate.

Space complexity is the extra memory an algorithm needs as n grows, usually not counting the input. Recursion does use space: each pending call keeps a stack frame, so depth d costs O(d). Binary search is O(1) space as a loop and O(log n) recursive.

Follow-up: can you do it in O(1) space? Usually by working in place with pointers.

Amortized O(1) means one operation can be slow, but n operations cost O(n) in total. A dynamic array copies everything into a bigger block when full, an O(n) step, but capacity grows by a constant factor (about 1.125× in CPython, 1.5× in OpenJDK's ArrayList), so the copies add up to O(n). The Java ArrayList docs promise only the amortized cost, not the factor.

import sys

items = []
last = sys.getsizeof(items)
for i in range(40):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:
        print(f"len {len(items):>2}: {size} bytes")
        last = size

Only 6 of the 40 appends changed the allocation.

These CPython average costs come up most:

• O(1): lst[i], append (amortized), lst.pop(), popleft(), set and dict lookup.
• O(log n): heappush, heappop.
• O(n): lst.pop(0), insert(0, x), x in lst, lst[:]; a k-item slice is O(k).
• O(n log n): sorted(lst).

The hidden O(n²) is if x in some_list inside a loop; use a set.

Write the recurrence and solve it. Merge sort is T(n) = 2T(n/2) + O(n): log₂ n levels of O(n) merging, so O(n log n). Others to know: binary search T(n/2) + O(1) is O(log n); recursive sum T(n-1) + O(1) is O(n); all subsets 2T(n-1) + O(1) is O(2^n); naive Fibonacci T(n-1) + T(n-2) is O(1.618^n), quoted as O(2^n). The master theorem covers T(n) = aT(n/b) + f(n), not T(n-1) ones.

Big O is an upper bound on how a function grows, Big Omega (Ω) a lower bound, and Big Theta (Θ) both at once, a tight bound. They are not the same as worst and best case: each case has its own bounds. Insertion sort takes Θ(n²) in the worst case and Θ(n) on sorted input, so its running time is O(n²) and Ω(n); merge sort is Θ(n log n) in every case. In interviews "O" usually means the tight worst case.

With two inputs of independent sizes, keep both variables. Steps done one after the other add: a pass over a then a pass over b is O(n + m). Nested steps multiply: scanning b for every item of a is O(n × m). Do not collapse either to O(n), since m can be far larger than n.

def common_slow(a, b):      # O(n * m): `x in b` scans the list each time
    return [x for x in a if x in b]

def common_fast(a, b):      # O(n + m): build a set once, then O(1) lookups
    seen = set(b)
    return [x for x in a if x in seen]

a, b = [1, 2, 3, 4], [3, 4, 5]
print(common_slow(a, b), common_fast(a, b))

Graph algorithms are written the same way: BFS is O(V + E).

Yes, for small inputs. Big O drops constant factors and only describes growth, so an algorithm doing very little work per step can win until n gets large. Insertion sort beats merge sort on short arrays, which is why Python's Timsort and Java's object sort use insertion sort for small runs, and Java's primitive quicksort switches to it for small ranges. Cache-friendly array scans can also beat pointer-heavy structures with a better Big O. Watch insertion sort.