Big-O Time Complexity Interview Questions

1. Nested loopsEasy

To find customers on both the email list (a, n items) and the SMS list (b, m items), this checks every pair. What is the time complexity?

for x in a:
    for y in b:
        if x == y:
            print(x)

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

2. Sequential loopsEasy

A report prints every order (a, n items), then every refund (b, m items). What is the time complexity?

for x in a:
    print(x)
for y in b:
    print(y)

1. O(n)
2. O(n + m)
3. O(n · m)
4. O(max(n, m)²)

3. Logarithmic loopsEasy

A pagination helper keeps halving the range n until one item is left. What is the time complexity?

while n > 1:
    n //= 2

1. O(1)
2. O(log n)
3. O(n)
4. O(n / 2)

4. ConstantsEasy

Every user gets exactly 5 notification checks. What's the time complexity?

for i in range(n):
    for j in range(5):
        total += i * j

1. O(n)
2. O(n²)
3. O(5n²)
4. O(n log n)

5. Nested loopsEasy

Comparing every pair of users for duplicates, without repeats. What's the time complexity?

for i in range(n):
    for j in range(i, n):
        total += 1

1. O(n)
2. O(n log n)
3. O(n²)
4. O(2ⁿ)

6. GraphsEasy

A friend-suggestion feature runs BFS over a social graph stored as adjacency lists: V users, E friendships. What's its time complexity?

1. O(V)
2. O(E)
3. O(V + E)
4. O(V · E)

7. Data structuresEasy

A loop runs x in items a million times. In Python, what's the average cost of each check when items is a list, and when it's a set?

1. O(1) and O(1)
2. O(n) and O(1)
3. O(log n) and O(1)
4. O(n) and O(log n)

8. SortingEasy

You pick merge sort for 2 GB of log lines on a box with 3 GB of RAM. What are its time and extra space complexity?

1. O(n log n) time, O(1) space
2. O(n log n) time, O(n) space
3. O(n²) time, O(1) space
4. O(n) time, O(n) space

9. StringsMedium

This Java export builds a CSV with 200,000 rows. Which review comment matters most?

String csv = "";
for (Row r : rows) {
    csv += r.toCsv() + "\n";
}

1. Use a ternary to build each line instead
2. Each += copies the whole string so far: O(n²); use a StringBuilder
3. Rename csv to output for clarity
4. Use \r\n line endings so Excel opens it correctly

10. Combining stepsMedium

You sort n items once, then answer n lookups with binary search. Total time?

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

11. SortingMedium

Quicksort always picks the first element as the pivot. What is its time on an already-sorted array?

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

12. Hidden loopsMedium

As the business grew 10×, this nightly job got 100× slower. Why?

vip_ids = [v.id for v in vips]
for c in customers:
    if c.id in vip_ids:
        tag(c)

1. tag is slow, and it now runs 10× more often
2. in on a list scans it: O(customers × vips), both grew 10×
3. Building vip_ids with a comprehension is quadratic
4. Python slows down as memory use grows

13. Space complexityMedium

A DP solution for the longest common subsequence of strings with lengths n and m fills a full table. How much space does it use, and how low can it go if you only need the length?

1. O(n · m), down to O(min(n, m))
2. O(n + m), down to O(1)
3. O(n · m), can't be reduced
4. O(2ⁿ), down to O(n)

14. RecursionMedium

A teammate's recursive Fibonacci returns instantly for n = 30 but seems to hang at n = 50. What's its time complexity?

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

1. O(n)
2. O(n²)
3. O(2ⁿ)
4. O(n log n)

15. Back-of-envelopeMedium

Your O(n²) solution runs on n = 100,000, and the machine does about 10⁸ simple operations per second. Roughly how long does it take?

1. About 0.1 seconds
2. About 1 second
3. About 100 seconds
4. About 3 hours