Time Complexity Questions with Answers (Big-O Practice)

Interviewers often show a loop and ask for its Big-O. Work out each one before revealing the answer.

1. Q1. What is the time complexity of accessing an array element by index?

   • A. O(n log n)
   • B. O(1)
   • C. O(n)
   • D. O(log n)
   Show answerHide answer

   Answer: B. O(1)
   The address is computed directly from the index.

2. Q2. What is the time complexity of linear search?

   • A. O(log n)
   • B. O(1)
   • C. O(n²)
   • D. O(n)
   Show answerHide answer

   Answer: D. O(n)
   In the worst case every element is checked.

3. Q3. What is the time complexity of binary search?

   • A. O(n log n)
   • B. O(n)
   • C. O(1)
   • D. O(log n)
   Show answerHide answer

   Answer: D. O(log n)
   Each step halves the search space.

4. Q4. What is the time complexity of two nested loops that each run n times?

   • A. O(n²)
   • B. O(n)
   • C. O(2n)
   • D. O(log n)
   Show answerHide answer

   Answer: A. O(n²)
   n × n iterations.

5. Q5. A loop where i doubles each time (i = 1, 2, 4, 8 … < n) runs how many times?

   • A. O(√n)
   • B. O(n)
   • C. O(n²)
   • D. O(log n)
   Show answerHide answer

   Answer: D. O(log n)
   Doubling reaches n after about log₂ n steps.

6. Q6. What is the time complexity of merge sort?

   • A. O(n²)
   • B. O(log n)
   • C. O(n log n) in every case
   • D. O(n)
   Show answerHide answer

   Answer: C. O(n log n) in every case
   log n levels of splitting, O(n) merging per level.

7. Q7. What is the average time complexity of quick sort?

   • A. O(n²)
   • B. O(n)
   • C. O(log n)
   • D. O(n log n)
   Show answerHide answer

   Answer: D. O(n log n)
   The worst case is O(n²) with consistently bad pivots.

8. Q8. What is the time complexity of bubble sort in the worst case?

   • A. O(1)
   • B. O(n²)
   • C. O(n log n)
   • D. O(n)
   Show answerHide answer

   Answer: B. O(n²)
   Up to n passes of n comparisons.

9. Q9. What is the best-case time of bubble sort with an early-exit flag on a sorted array?

   • A. O(n²)
   • B. O(n)
   • C. O(log n)
   • D. O(1)
   Show answerHide answer

   Answer: B. O(n)
   One pass with no swaps proves it is sorted.

10. Q10. What is the time complexity of recursive Fibonacci without memoization?

    • A. O(log n)
    • B. O(n²)
    • C. O(2ⁿ)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(2ⁿ)
    Each call branches into two more calls.

11. Q11. What is the time complexity of Fibonacci with memoization?

    • A. O(n)
    • B. O(log n)
    • C. O(n²)
    • D. O(2ⁿ)
    Show answerHide answer

    Answer: A. O(n)
    Each value from 0 to n is computed once.

12. Q12. What is the space complexity of merge sort on an array?

    • A. O(log n)
    • B. O(n)
    • C. O(1)
    • D. O(n²)
    Show answerHide answer

    Answer: B. O(n)
    It needs a temporary array for merging.

13. Q13. What is the space complexity of an in-place reversal of an array?

    • A. O(n)
    • B. O(log n)
    • C. O(1)
    • D. O(n²)
    Show answerHide answer

    Answer: C. O(1)
    Only a temporary variable for swapping.

14. Q14. What is the average time to insert a key into a hash table?

    • A. O(n)
    • B. O(log n)
    • C. O(n log n)
    • D. O(1)
    Show answerHide answer

    Answer: D. O(1)
    Worst case is O(n) when many keys collide.

15. Q15. What is the time to search in a balanced binary search tree?

    • A. O(1)
    • B. O(n)
    • C. O(log n)
    • D. O(n²)
    Show answerHide answer

    Answer: C. O(log n)
    The height is about log n.

16. Q16. What is the time complexity of BFS or DFS on a graph with V vertices and E edges (adjacency list)?

    • A. O(V × E)
    • B. O(V + E)
    • C. O(V²)
    • D. O(E log V)
    Show answerHide answer

    Answer: B. O(V + E)
    Every vertex and edge is visited once.

17. Q17. What is the time complexity of Dijkstra's algorithm with a binary heap?

    • A. O(V + E)
    • B. O((V + E) log V)
    • C. O(V³)
    • D. O(E²)
    Show answerHide answer

    Answer: B. O((V + E) log V)
    Each edge relaxation may push to the heap.

18. Q18. Which grows fastest as n increases?

    • A. O(n³)
    • B. O(2ⁿ)
    • C. O(n log n)
    • D. O(n²)
    Show answerHide answer

    Answer: B. O(2ⁿ)
    Exponential beats any polynomial.

19. Q19. Which grows slowest as n increases?

    • A. O(√n)
    • B. O(log n)
    • C. O(n)
    • D. O(n log n)
    Show answerHide answer

    Answer: B. O(log n)
    Logarithms grow very slowly: log₂ of a million is about 20.

20. Q20. What is the time complexity of generating all permutations of n items?

    • A. O(n!)
    • B. O(2ⁿ)
    • C. O(n log n)
    • D. O(n²)
    Show answerHide answer

    Answer: A. O(n!)
    There are n! permutations.

21. Q21. What is the time complexity of generating all subsets of n items?

    • A. O(n²)
    • B. O(n!)
    • C. O(2ⁿ)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(2ⁿ)
    Each item is either in or out of a subset.

22. Q22. What does Big-O notation describe?

    • A. An upper bound on how an algorithm's cost grows with input size
    • B. The number of lines of code
    • C. The exact running time in seconds
    • D. The memory address of a variable
    Show answerHide answer

    Answer: A. An upper bound on how an algorithm's cost grows with input size
    Constants and lower-order terms are dropped.

23. Q23. What is O(3n² + 5n + 100) simplified?

    • A. O(n²)
    • B. O(n² + n)
    • C. O(3n²)
    • D. O(100)
    Show answerHide answer

    Answer: A. O(n²)
    Keep the fastest-growing term and drop constants.

24. Q24. What is the time complexity of finding the maximum in an unsorted array?

    • A. O(n)
    • B. O(1)
    • C. O(log n)
    • D. O(n log n)
    Show answerHide answer

    Answer: A. O(n)
    Every element must be seen once.

25. Q25. What is the time complexity of finding the maximum in a max-heap?

    • A. O(n log n)
    • B. O(log n)
    • C. O(1)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(1)
    It is the root.

26. Q26. What is the time complexity of building a heap from n elements with heapify?

    • A. O(n²)
    • B. O(log n)
    • C. O(n)
    • D. O(n log n)
    Show answerHide answer

    Answer: C. O(n)
    A surprising result: most nodes are near the bottom and sift down little.

27. Q27. What is the time complexity of heap sort?

    • A. O(n²)
    • B. O(log n)
    • C. O(n log n)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(n log n)
    n removals, each O(log n).

28. Q28. What is the amortised time of appending to a dynamic array (ArrayList, vector, Python list)?

    • A. O(log n)
    • B. O(1)
    • C. O(n)
    • D. O(n²)
    Show answerHide answer

    Answer: B. O(1)
    Occasional resizing is spread over many cheap appends.

29. Q29. What is the time complexity of inserting at the beginning of an array of n elements?

    • A. O(n²)
    • B. O(n)
    • C. O(1)
    • D. O(log n)
    Show answerHide answer

    Answer: B. O(n)
    All elements shift one place right.

30. Q30. What is the time complexity of inserting at the head of a linked list?

    • A. O(log n)
    • B. O(n²)
    • C. O(1)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(1)
    Only the head pointer changes.

31. Q31. What is the space complexity of a recursive function that recurses n levels deep?

    • A. O(1)
    • B. O(n)
    • C. O(n²)
    • D. O(log n)
    Show answerHide answer

    Answer: B. O(n)
    Each level keeps a stack frame.

32. Q32. Checking whether a number n is prime by testing divisors up to √n is:

    • A. O(n)
    • B. O(1)
    • C. O(log n)
    • D. O(√n)
    Show answerHide answer

    Answer: D. O(√n)
    If n has a divisor, one of them is at most √n.

33. Q33. What is the time complexity of the Sieve of Eratosthenes up to n?

    • A. O(√n)
    • B. O(n log log n)
    • C. O(n)
    • D. O(n²)
    Show answerHide answer

    Answer: B. O(n log log n)
    Each number is crossed out by its prime factors.

34. Q34. A loop for (i = n; i > 0; i = i / 2) runs how many times?

    • A. O(n)
    • B. O(1)
    • C. O(log n)
    • D. O(n/2)
    Show answerHide answer

    Answer: C. O(log n)
    Halving reaches 0 after about log₂ n steps.

35. Q35. What is the time complexity of matrix multiplication of two n × n matrices with three nested loops?

    • A. O(n²)
    • B. O(n log n)
    • C. O(2ⁿ)
    • D. O(n³)
    Show answerHide answer

    Answer: D. O(n³)
    n² cells, each needing n multiplications.

36. Q36. Two separate (not nested) loops over n elements give what complexity?

    • A. O(n²)
    • B. O(2ⁿ)
    • C. O(log n)
    • D. O(n)
    Show answerHide answer

    Answer: D. O(n)
    n + n = 2n, which is O(n).

37. Q37. An outer loop of n with an inner loop for j = i to n runs about how many times?

    • A. O(n²)
    • B. O(n)
    • C. O(n log n)
    • D. O(n³)
    Show answerHide answer

    Answer: A. O(n²)
    n + (n − 1) + … + 1 = n(n + 1)/2.

38. Q38. What is the time complexity of checking whether two strings of length n are anagrams using a count array?

    • A. O(n²)
    • B. O(1)
    • C. O(n)
    • D. O(n log n)
    Show answerHide answer

    Answer: C. O(n)
    One pass to count, one to compare 26 counts.

39. Q39. What is the time complexity of the two-sum problem using a hash map?

    • A. O(n²)
    • B. O(n log n)
    • C. O(1)
    • D. O(n)
    Show answerHide answer

    Answer: D. O(n)
    Each lookup for the complement is O(1) on average.

40. Q40. Which is the best possible time for comparison-based sorting in the worst case?

    • A. O(log n)
    • B. O(n²)
    • C. O(n log n)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(n log n)
    A decision-tree argument shows you can't do better with comparisons alone.

41. Q41. What is the time complexity of this code, where size is the input size n?

    low, high = 0, size - 1
    while low <= high:
        mid = (low + high) // 2
        high = mid - 1

    • A. O(2ⁿ)
    • B. O(1)
    • C. O(log n)
    • D. O(n³)
    Show answerHide answer

    Answer: C. O(log n)
    The range is halved every step, like binary search.

42. Q42. What is the time complexity of this code, where size is the input size n?

    for i in range(size):
        for j in range(size):
            for k in range(size):
                pass

    • A. O(n)
    • B. O(n log n)
    • C. O(√n)
    • D. O(n³)
    Show answerHide answer

    Answer: D. O(n³)
    Three nested loops of n each.

43. Q43. What is the time complexity of this code, where n is the input size n?

    low, high = 0, n - 1
    while low <= high:
        mid = (low + high) // 2
        high = mid - 1

    • A. O(n²)
    • B. O(2ⁿ)
    • C. O(n)
    • D. O(log n)
    Show answerHide answer

    Answer: D. O(log n)
    The range is halved every step, like binary search.

44. Q44. What is the time complexity of this code, where n is the input size n?

    for i in range(n):
        for j in range(n):
            print(i, j)

    • A. O(n²)
    • B. O(1)
    • C. O(√n)
    • D. O(n log n)
    Show answerHide answer

    Answer: A. O(n²)
    Two nested loops, each running n times.

45. Q45. What is the time complexity of this code, where size is the input size n?

    x = size * 2 + 7
    print(x)

    • A. O(n²)
    • B. O(n³)
    • C. O(1)
    • D. O(√n)
    Show answerHide answer

    Answer: C. O(1)
    A fixed number of steps regardless of n.

46. Q46. What is the time complexity of this code, where count is the input size n?

    for i in range(count):
        for j in range(10):
            print(i * j)

    • A. O(1)
    • B. O(n)
    • C. O(log n)
    • D. O(n²)
    Show answerHide answer

    Answer: B. O(n)
    The inner loop always runs 10 times (a constant), so it's 10n = O(n).

47. Q47. What is the time complexity of this code, where size is the input size n?

    for i in range(size):
        for j in range(i):
            print(j)

    • A. O(n³)
    • B. O(n²)
    • C. O(1)
    • D. O(n)
    Show answerHide answer

    Answer: B. O(n²)
    0 + 1 + … + (n−1) = n(n−1)/2 steps, which is O(n²).

48. Q48. What is the time complexity of this code, where size is the input size n?

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

    • A. O(n³)
    • B. O(√n)
    • C. O(2ⁿ)
    • D. O(1)
    Show answerHide answer

    Answer: C. O(2ⁿ)
    Each call makes two more calls, so the number of calls roughly doubles at every level.

49. Q49. What is the time complexity of this code, where count is the input size n?

    i = 1
    while i < count:
        i = i * 2

    • A. O(n²)
    • B. O(2ⁿ)
    • C. O(log n)
    • D. O(n³)
    Show answerHide answer

    Answer: C. O(log n)
    i doubles each time, so the loop runs about log₂ n times.

50. Q50. What is the time complexity of this code, where size is the input size n?

    for i in range(size):
        for j in range(size):
            print(i, j)

    • A. O(log n)
    • B. O(√n)
    • C. O(n²)
    • D. O(n)
    Show answerHide answer

    Answer: C. O(n²)
    Two nested loops, each running n times.

51. Q51. What is the time complexity of this code, where n is the input size n?

    for i in range(n):
        j = 1
        while j < n:
            j *= 2

    • A. O(n log n)
    • B. O(√n)
    • C. O(2ⁿ)
    • D. O(n³)
    Show answerHide answer

    Answer: A. O(n log n)
    The outer loop runs n times and the inner one log n times.

52. Q52. What is the time complexity of this code, where n is the input size n?

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

    • A. O(n³)
    • B. O(2ⁿ)
    • C. O(1)
    • D. O(√n)
    Show answerHide answer

    Answer: B. O(2ⁿ)
    Each call makes two more calls, so the number of calls roughly doubles at every level.