Time & Space Complexity (Big-O) interview questions

25 questions from the Time & Space Complexity (Big-O) course, each with the correct answer and an explanation. Try to answer before you open the answer.

Why We Analyse Algorithms

1. What does complexity analysis primarily describe?

  1. How the work grows as the input size grows
  2. The exact running time in seconds
  3. The number of lines of code
  4. The programming language used
Show answer

Answer: How the work grows as the input size grows

Complexity describes growth as a function of n, independent of machine details.

Lesson: Measuring Algorithms Without a Stopwatch

3. Which growth rate is the smallest for large n?

  1. O(n)
  2. O(n log n)
  3. O(log n)
  4. O(√n)
Show answer

Answer: O(log n)

Logarithmic growth is slower than any polynomial power of n, including √n.

Lesson: The Common Growth Rates

Asymptotic Notation

4. Which statement is true by the definition of Big-O?

  1. 2n + 100 is O(1)
  2. n³ is O(n²)
  3. 7n² + n is O(n²)
  4. n log n is O(n)
Show answer

Answer: 7n² + n is O(n²)

Constants and lower-order terms are absorbed; the n² term dominates.

Lesson: Big-O: The Formal Definition

5. What does f(n) = Θ(g(n)) mean?

  1. f grows strictly slower than g
  2. f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g
  3. f is always smaller than g
  4. f and g are equal for all n
Show answer

Answer: f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g

Theta is a tight bound: f is bounded above and below by constant multiples of g.

Lesson: Big-Omega, Big-Theta and Little-o

6. A function loops over a list of n items and, inside the loop, does a binary search on a sorted array of size m. What is its complexity?

  1. O(n log m)
  2. O(n + m)
  3. O(n²)
  4. O(log n)
Show answer

Answer: O(n log m)

n iterations each costing O(log m) multiply to O(n log m).

Lesson: Rules for Simplifying Complexity

Analysing Loops

7. What is the complexity of `for i in range(n): for j in range(i, n): work()` with constant-time work?

  1. O(n²)
  2. O(n)
  3. O(n log n)
  4. O(n³)
Show answer

Answer: O(n²)

The inner loop runs n + (n−1) + … + 1 = n(n+1)/2 times in total, which is O(n²).

Lesson: Single, Nested and Dependent Loops

8. How many iterations does `i = n; while i > 1: i = i // 2` perform, roughly?

  1. n
  2. n / 2
  3. √n
  4. log₂ n
Show answer

Answer: log₂ n

Halving n repeatedly reaches 1 after about log₂ n steps.

Lesson: Logarithmic and Square-Root Loops

9. In a sliding-window algorithm, the right pointer advances n times and the left pointer advances at most n times in total. What is the overall complexity?

  1. O(n²)
  2. O(n log n)
  3. O(n)
  4. O(log n)
Show answer

Answer: O(n)

Total pointer movement is at most 2n, so the work is linear.

Lesson: Tricky Loop Patterns

Analysing Recursion

10. Which recurrence describes binary search?

  1. T(n) = 2T(n/2) + O(n)
  2. T(n) = T(n − 1) + O(n)
  3. T(n) = T(n/2) + O(1)
  4. T(n) = 2T(n − 1) + O(1)
Show answer

Answer: T(n) = T(n/2) + O(1)

Binary search does constant work and recurses on one half of the input.

Lesson: Writing Recurrence Relations

11. Why is naive recursive Fibonacci exponential?

  1. It uses a loop inside the recursion
  2. It recomputes the same subproblems many times, with the call tree branching twice at each level
  3. Python recursion is slow
  4. It stores every result in memory
Show answer

Answer: It recomputes the same subproblems many times, with the call tree branching twice at each level

Overlapping subproblems are recomputed, so the number of calls grows exponentially.

Lesson: Recursion Trees and Exponential Recursion

12. Using the master theorem, what is T(n) = 4T(n/2) + n?

  1. Θ(n²)
  2. Θ(n)
  3. Θ(n log n)
  4. Θ(n² log n)
Show answer

Answer: Θ(n²)

log₂ 4 = 2, so n^(log_b a) = n², which dominates f(n) = n: case 1 gives Θ(n²).

Lesson: The Master Theorem

Space Complexity

13. What is the auxiliary space of reversing an array in place by swapping elements from both ends?

  1. O(1)
  2. O(n)
  3. O(log n)
  4. O(n²)
Show answer

Answer: O(1)

Only a constant number of index variables are used, regardless of n.

Lesson: Measuring Memory Use

14. What is the stack space used by a recursive function that recurses on n − 1 until reaching 0?

  1. O(1)
  2. O(log n)
  3. O(n²)
  4. O(n)
Show answer

Answer: O(n)

The recursion is n levels deep, so n frames exist at the deepest point.

Lesson: Recursion and the Call Stack

15. Prefix sums answer each range-sum query in O(1). What do they cost?

  1. Nothing
  2. O(n²) space
  3. O(n) preprocessing time and O(n) extra space
  4. O(log n) per query
Show answer

Answer: O(n) preprocessing time and O(n) extra space

Building the prefix array takes linear time and memory, paid once.

Lesson: Time-Space Trade-offs

Complexity of Data Structure Operations

16. What is the amortised cost of appending to a dynamic array that doubles its capacity when full?

  1. O(n)
  2. O(log n)
  3. O(1)
  4. O(n²)
Show answer

Answer: O(1)

Occasional O(n) copies average out to a constant per append because capacity grows geometrically.

Lesson: Arrays, Dynamic Arrays and Linked Lists

17. You need to repeatedly extract the smallest element while inserting new ones. Which structure fits best?

  1. Hash table
  2. Binary heap (priority queue)
  3. Unsorted array
  4. Linked list
Show answer

Answer: Binary heap (priority queue)

Heaps give O(log n) insert and remove-min with O(1) access to the minimum.

Lesson: Hash Tables, Trees and Heaps

18. What is the cost of `x in my_list` for a Python list of n elements?

  1. O(n)
  2. O(1)
  3. O(log n)
  4. O(n log n)
Show answer

Answer: O(n)

Membership in a list is a linear scan; use a set for average O(1) membership tests.

Lesson: Library Call Costs in Practice

Amortised Analysis, Sorting Bounds and Complexity Classes

19. Why is appending to a doubling dynamic array amortised O(1) even though some appends cost O(n)?

  1. The total copying cost over n appends is less than about n, so the average per append is constant
  2. Resizes never happen
  3. Copying is free in modern hardware
  4. Amortised means best case
Show answer

Answer: The total copying cost over n appends is less than about n, so the average per append is constant

Geometric growth makes the sum of all copies linear in n.

Lesson: Amortised Analysis

20. Why can counting sort run faster than Ω(n log n)?

  1. It uses better comparisons
  2. It only works on sorted input
  3. It ignores half the elements
  4. It is not comparison-based; it uses the integer values directly within a known range
Show answer

Answer: It is not comparison-based; it uses the integer values directly within a known range

The lower bound applies only to comparison sorts; counting sort indexes by key value.

Lesson: Sorting Complexities and the Lower Bound

21. Why is the O(n · W) knapsack algorithm called pseudo-polynomial?

  1. It runs in O(n) time
  2. It only approximates the answer
  3. Its running time is polynomial in the value W, but exponential in the number of bits used to represent W
  4. It requires quantum computers
Show answer

Answer: Its running time is polynomial in the value W, but exponential in the number of bits used to represent W

Input size counts the digits of W, and W can be exponentially large in that digit count.

Lesson: P, NP and Intractable Problems

Applying Complexity in Practice and Revision

22. What does the hash-map solution to two-sum trade to achieve O(n) time?

  1. Correctness
  2. Sorting stability
  3. O(n) extra space for the map
  4. Recursion depth
Show answer

Answer: O(n) extra space for the map

Storing seen values in a hash map uses linear extra memory to avoid the inner loop.

Lesson: From Brute Force to Efficient Solutions

23. A problem has n ≤ 200,000 and a one-second limit. Which complexity is most likely expected?

  1. O(n³)
  2. O(n log n)
  3. O(2ⁿ)
  4. O(n!)
Show answer

Answer: O(n log n)

With n around 2 × 10⁵, O(n²) is about 4 × 10¹⁰ operations, too many; O(n log n) fits easily.

Lesson: Reading Constraints to Pick an Approach

24. Why might an O(n log n) algorithm beat an O(n) algorithm in practice for realistic input sizes?

  1. Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference
  2. Big-O is always wrong
  3. O(n log n) is always faster
  4. log n is negative for large n
Show answer

Answer: Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference

Asymptotic notation hides constants and hardware effects that dominate for moderate n.

Lesson: Pitfalls and Real-World Performance

25. What is the solution of T(n) = T(n/2) + n?

  1. Θ(log n)
  2. Θ(n log n)
  3. Θ(n²)
  4. Θ(n)
Show answer

Answer: Θ(n)

n + n/2 + n/4 + … < 2n, so the root's linear work dominates: Θ(n) (master theorem case 3).

Lesson: Revision and Interview Questions

← Back to the course