Big O Notation — Time and Space Complexity Explained
The Interview Question
Explain Big O notation. How do you determine the time and space complexity of an algorithm?
Expert Answer
Big O notation describes how an algorithm's runtime or memory usage grows as the input size increases. It captures the worst-case upper bound, ignoring constants and lower-order terms. O(1) means constant time — the operation takes the same time regardless of input size (hash table lookup). O(log n) means logarithmic — each step halves the problem (binary search). O(n) means linear — you touch every element once (array scan). O(n log n) is the best possible comparison-based sort (merge sort, quicksort average). O(n²) means quadratic — nested loops over the input (bubble sort, brute-force pair matching). O(2^n) is exponential — common in naive recursive solutions (fibonacci without memoization). To analyze an algorithm: count the number of operations as a function of n, drop constants (2n → O(n)), drop lower-order terms (n² + n → O(n²)), and consider the worst case. Space complexity follows the same logic but counts memory allocation instead of operations.
Key Points to Hit in Your Answer
- Big O describes growth rate, not exact speed — O(n) doesn't mean n milliseconds
- Drop constants: O(2n) = O(n), O(n/2) = O(n)
- Drop lower terms: O(n² + n) = O(n²)
- Common complexities ranked: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
- Amortized analysis: occasional expensive operations averaged over many cheap ones (dynamic array append)
- Space complexity includes auxiliary space (extra allocations), not the input itself
Code Example
# O(1) — constant
def get_first(arr):
return arr[0] # always one operation
# O(log n) — logarithmic (binary search)
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi: # halves search space each iteration
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
# O(n) — linear
def find_max(arr):
max_val = arr[0]
for x in arr: # touches every element once
max_val = max(max_val, x)
return max_val
# O(n²) — quadratic
def has_duplicate_brute(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)): # nested loop
if arr[i] == arr[j]: return True
return False
# O(n) — same problem, better algorithm
def has_duplicate_set(arr):
seen = set() # O(n) space tradeoff
for x in arr:
if x in seen: return True
seen.add(x)
return FalseWhat Interviewers Are Really Looking For
They want to see you analyze code, not just label it. Walk through the has_duplicate example: brute force is O(n²) because of nested loops, the set approach is O(n) time with O(n) space — that tradeoff is the core of algorithm design. Being able to identify 'this nested loop is actually O(n), not O(n²)' in tricky cases (like two pointers) shows real understanding.
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →