Asymptotic Worst-Case Time Complexity MCQs (GATE – Algorithms)
Q1. If an algorithm’s running time is given by T(n) = 3n³ + 5n² + 10, what is its asymptotic worst-case time complexity?
A) O(n²)
B) O(n³)
C) O(n)
D) O(log n)
✅ Answer: B
Explanation: Highest order term dominates → O(n³).
Q2. For an algorithm with T(n) = n log n + 100n, asymptotic worst-case complexity is:
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
✅ Answer: B
Explanation: Dominant term = n log n → O(n log n).
Q3. If T(n) = 5T(n/2) + n², what is the asymptotic time complexity?
A) O(n² log n)
B) O(n²)
C) O(n^(log₂5))
D) O(n³)
✅ Answer: C
Explanation: Using Master Theorem, a = 5, b = 2 → n^(log₂5) ≈ n².32 dominates.
Q4. The function 2ⁿ grows asymptotically faster than:
A) n³
B) n log n
C) n!
D) Both A and B
✅ Answer: D
Explanation: 2ⁿ > all polynomial functions asymptotically.
Q5. If an algorithm takes T(n) = 4T(n/2) + n, its asymptotic bound is:
A) O(n²)
B) O(n log n)
C) O(n)
D) O(n² log n)
✅ Answer: A
Explanation: By Master Theorem, a=4, b=2, f(n)=n ⇒ n^(log₂4)=n² > n → O(n²).
Q6. The asymptotic complexity of matrix multiplication using Strassen’s algorithm is:
A) O(n³)
B) O(n².81)
C) O(n²)
D) O(n log n)
✅ Answer: B
Explanation: Strassen’s method reduces complexity to O(n^2.81).
Q7. If an algorithm requires O(n²) operations for input size n = 500, doubling n will approximately multiply execution time by:
A) 2
B) 4
C) 8
D) 16
✅ Answer: B
Explanation: Quadratic growth → (2n)² = 4× more operations.
Q8. Given T(n) = 2T(n/2) + n², time complexity = ?
A) O(n²)
B) O(n log n)
C) O(n² log n)
D) O(n³)
✅ Answer: C
Explanation: a=2, b=2 → n^(log₂2)=n; f(n)=n² dominates → O(n² log n).
Q9. If algorithm A has complexity O(n²) and algorithm B has O(n log n), which performs better for large n?
A) A
B) B
C) Both same
D) Depends on constants
✅ Answer: B
Explanation: n log n grows slower than n² for large n.
Q10. If T(n) = 7T(n/2) + n², asymptotic complexity is:
A) O(n²)
B) O(n³)
C) O(n^(log₂7))
D) O(n² log n)
✅ Answer: C
Explanation: log₂7 ≈ 2.807 → O(n^2.807).
Q11. Which of the following grows fastest asymptotically?
A) n² log n
B) 2ⁿ
C) n³
D) n!
✅ Answer: D
Explanation: n! > 2ⁿ > n³ > n² log n for large n.
Q12. If f(n) = O(g(n)), which statement is true?
A) f(n) grows faster
B) f(n) grows slower or equal
C) f(n) grows exponentially
D) None
✅ Answer: B
Explanation: Big-O gives upper bound; f(n) ≤ constant × g(n).
Q13. The asymptotic worst-case time for binary search is:
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
✅ Answer: B
Explanation: Each comparison halves the search space.
Q14. Which of the following is asymptotically smallest?
A) n log n
B) n²
C) log² n
D) n
✅ Answer: C
Explanation: log² n grows slower than any linear or superlinear function.
Q15. For recurrence T(n) = T(n−1) + n, the asymptotic time complexity is:
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
✅ Answer: C
Explanation: Summing series n + (n−1) + … + 1 = O(n²).
Q16. An algorithm’s running time doubles whenever input size increases by 1. The time complexity is approximately:
A) O(n)
B) O(2ⁿ)
C) O(log n)
D) O(n²)
✅ Answer: B
Explanation: Doubling time per unit growth implies exponential.
Q17. If T(n) = T(n/4) + 1, what’s its complexity?
A) O(log n)
B) O(n)
C) O(1)
D) O(n log n)
✅ Answer: A
Explanation: Problem size reduces exponentially → O(log n).
Q18. If an algorithm runs in O(n log n), and takes 2 ms for n = 1,000, what’s approximate time for n = 8,000?
A) 16 ms
B) 24 ms
C) 48 ms
D) 64 ms
✅ Answer: C
Explanation: (n log n) ratio ≈ 8×(log 8000 / log 1000) ≈ 8×1.26 ≈ 10× increase → 2×10=20 ms → ~48 ms including constants.
Q19. The time complexity of insertion sort in worst case is:
A) O(n²)
B) O(n log n)
C) O(log n)
D) O(n)
✅ Answer: A
Explanation: Each insertion may compare with all previous elements → n(n−1)/2 comparisons.
Q20. For Quick Sort in worst case, time complexity is:
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
✅ Answer: B
Explanation: Unbalanced partitions lead to quadratic recursion.
Q21. If T(n) = 3T(n/3) + n, what’s complexity?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
✅ Answer: B
Explanation: a=b=3 → f(n)=n same as n^(log₃3)=n → O(n log n).
Q22. Which asymptotic notation gives a tight bound?
A) O
B) Ω
C) Θ
D) None
✅ Answer: C
Explanation: Θ provides both upper and lower bounds.
Q23. Which grows faster asymptotically?
A) n log n
B) n^1.5
C) n²
D) n!
✅ Answer: D
Explanation: n! dominates all polynomial functions.
Q24. The asymptotic worst-case complexity of Heap Sort is:
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
✅ Answer: A
Explanation: Both heap construction and deletions take O(n log n).
Q25. For T(n) = 2T(n/2) + n log n, complexity = ?
A) O(n log² n)
B) O(n log n)
C) O(n²)
D) O(n³)
✅ Answer: A
Explanation: f(n)=n log n > n^(log₂2)=n → O(n log² n).
Q26. The function n^(1.5) grows faster than:
A) n log n
B) n²
C) 2ⁿ
D) n!
✅ Answer: A
Explanation: 1.5 > 1, so n^1.5 > n log n asymptotically.
Q27. If algorithm A takes O(n²) and B takes O(2ⁿ), which is better for large n?
A) A
B) B
C) Both same
D) Cannot determine
✅ Answer: A
Explanation: Exponential growth dominates polynomial growth.
Q28. The asymptotic complexity of computing Fibonacci recursively is:
A) O(2ⁿ)
B) O(n²)
C) O(n log n)
D) O(n)
✅ Answer: A
Explanation: Recursive calls branch exponentially.
Q29. Merge Sort’s worst case asymptotic complexity is:
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
✅ Answer: B
Explanation: Divide and conquer always yields O(n log n).
Q30. An algorithm performs n³ + 4n log n + 7 operations. Its asymptotic time complexity = ?
A) O(n³)
B) O(n log n)
C) O(log n)
D) O(n²)
✅ Answer: A
Explanation: Highest-order term dominates.
💠 Asymptotic Worst-Case Time Complexity — GATE Level MCQs (Q31–Q100)
Q31. The time complexity of binary search on a sorted array of 1024 elements is approximately equal to:
A) 5
B) 8
C) 10
D) 100
✅ Answer: C
Explanation: log₂(1024) = 10 → at most 10 comparisons in worst case → O(log n).
Q32. If T(n) = 4T(n/3) + n, the asymptotic complexity is:
A) O(n)
B) O(n log n)
C) O(n^(log₃4))
D) O(n²)
✅ Answer: C
Explanation: log₃4 ≈ 1.26 → O(n^1.26) by Master Theorem.
Q33. If an algorithm has complexity O(√n), doubling the input size multiplies running time by approximately:
A) 1.4
B) 2
C) 3
D) 4
✅ Answer: A
Explanation: √(2n)/√n = √2 ≈ 1.414.
Q34. The asymptotic complexity of computing factorial using recursion is:
A) O(n)
B) O(n²)
C) O(2ⁿ)
D) O(log n)
✅ Answer: A
Explanation: Each recursive call decrements n by 1 → n calls → O(n).
Q35. If T(n) = T(n/2) + O(1), complexity is:
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
✅ Answer: B
Explanation: Reducing problem size by half each time → logarithmic depth recursion.
Q36. Which function dominates asymptotically?
A) n² log n
B) n²
C) n log² n
D) n² + n log n
✅ Answer: A
Explanation: n² log n > n² for large n.
Q37. The function log₁₀n is asymptotically equivalent to:
A) log₂n
B) n
C) n²
D) 2ⁿ
✅ Answer: A
Explanation: All logarithms differ only by constant factor → Θ(log n).
Q38. The function 3ⁿ grows asymptotically faster than:
A) 2ⁿ
B) n³
C) n log n
D) All of these
✅ Answer: D
Explanation: Exponential dominates all polynomial/logarithmic functions.
Q39. For T(n) = T(n/2) + n², the asymptotic bound is:
A) O(n²)
B) O(n² log n)
C) O(n log n)
D) O(log n)
✅ Answer: A
Explanation: f(n)=n² dominates n^(log₂1)=n⁰ → O(n²).
Q40. If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = ?
A) O(h(n))
B) Θ(h(n))
C) Ω(h(n))
D) None
✅ Answer: A
Explanation: Big-O is transitive → upper bound carries through.
Q41. Which of the following is not a valid asymptotic notation?
A) O(n log n)
B) Θ(n²)
C) Ω(n³)
D) µ(n log n)
✅ Answer: D
Explanation: µ notation does not exist in asymptotic analysis.
Q42. The asymptotic time complexity of linear search in a sorted array is:
A) O(log n)
B) O(n)
C) O(1)
D) O(n log n)
✅ Answer: B
Explanation: Even in sorted array, without binary search, each element must be checked.
Q43. If an algorithm runs in 0.5n³ + 20n² + 100n time, it belongs to:
A) O(n³)
B) O(n²)
C) O(n log n)
D) Θ(n)
✅ Answer: A
Explanation: Highest-order term dominates asymptotically.
Q44. If T(n) = 3T(n/2) + n, the asymptotic complexity is:
A) O(n log n)
B) O(n^(log₂3))
C) O(n²)
D) O(n)
✅ Answer: B
Explanation: log₂3 ≈ 1.585 → O(n^1.585).
Q45. The asymptotic complexity of the best comparison-based sorting algorithm is:
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
✅ Answer: B
Explanation: Lower bound for comparison-based sorting = Ω(n log n).
Q46. If f(n) = Θ(n²) and g(n) = Θ(n³), then f(n) = ?
A) o(g(n))
B) Ω(g(n))
C) Θ(g(n))
D) None
✅ Answer: A
Explanation: f grows slower than g → little-o relation.
Q47. Which one has the same asymptotic order as n³ + 100n² + 50?
A) O(n³)
B) O(n²)
C) O(n)
D) O(1)
✅ Answer: A
Explanation: Highest order term dominates.
Q48. Which asymptotic notation represents lower bound?
A) O
B) Θ
C) Ω
D) None
✅ Answer: C
Explanation: Ω provides asymptotic lower bound.
Q49. If an algorithm takes 5n log n + 10n time, the worst-case complexity is:
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n)
✅ Answer: A
Explanation: n log n dominates linear term.
Q50. Which one is the tightest bound for T(n) = n² + 5n log n + 100?
A) O(n³)
B) Θ(n²)
C) Ω(n² log n)
D) O(log n)
✅ Answer: B
Explanation: Dominant term n² → Θ(n²).
Q51. If T(n) = 2T(n/4) + √n, complexity = ?
A) O(n)
B) O(√n log n)
C) O(√n)
D) O(log n)
✅ Answer: C
Explanation: n^(log₄2)=√n, f(n)=√n → T(n)=Θ(√n log n) ≈ O(√n log n).
Q52. The asymptotic complexity of traversing a graph with BFS is:
A) O(V + E)
B) O(V²)
C) O(E log V)
D) O(log E)
✅ Answer: A
Explanation: Each vertex and edge is processed once.
Q53. If an algorithm requires n³/3 operations, its asymptotic complexity is:
A) O(n²)
B) O(n³)
C) O(n log n)
D) O(n)
✅ Answer: B
Explanation: Constants are ignored in asymptotic notation.
Q54. The function (n log n)² is asymptotically equal to:
A) O(n² log n)
B) O(n² log² n)
C) O(n³)
D) O(log n)
✅ Answer: B
Explanation: (n log n)² = n² log² n.
Q55. The time complexity of computing nth Fibonacci using iteration is:
A) O(n)
B) O(2ⁿ)
C) O(log n)
D) O(n²)
✅ Answer: A
Explanation: Each term computed once sequentially.
Q56. log(n!) is asymptotically equal to:
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n³)
✅ Answer: A
Explanation: Using Stirling’s approximation → log(n!) ≈ n log n − n.
Q57. The recurrence T(n) = 2T(n/2) + n/ log n results in:
A) O(n log n)
B) O(n)
C) O(n²)
D) O(n log log n)
✅ Answer: A
Explanation: f(n) smaller than n → T(n) = Θ(n log n).
Q58. If two functions f(n) = 10n² and g(n) = n² + log n, then f(n) = ?
A) Θ(g(n))
B) O(g(n))
C) Ω(g(n))
D) All of these
✅ Answer: D
Explanation: They are asymptotically identical up to constants.
Q59. The number of iterations in binary search for n elements is at most:
A) log₂n
B) n
C) n log n
D) log₁₀n
✅ Answer: A
Explanation: Each iteration halves array → O(log n).
Q60. For recurrence T(n) = T(n−1) + log n, asymptotic complexity is:
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n)
✅ Answer: A
Explanation: Summation log i from 1 to n ≈ O(n log n).
Q61. The asymptotic complexity of Dijkstra’s algorithm using min-heap is:
A) O(V²)
B) O(E log V)
C) O(V log V)
D) O(V + E)
✅ Answer: B
Explanation: Extract-min + decrease-key → O(E log V).
Q62. Which grows slower: log²n or √n?
A) log²n
B) √n
C) Same
D) Cannot be determined
✅ Answer: A
Explanation: √n grows polynomially faster than log²n.
Q63. If T(n) = T(n/3) + n², the time complexity is:
A) O(n²)
B) O(n² log n)
C) O(n³)
D) O(n log n)
✅ Answer: A
Explanation: f(n)=n² dominates → O(n²).
Q64. Which function dominates asymptotically?
A) n²
B) n²/log n
C) n log n
D) n³
✅ Answer: D
Explanation: n³ grows faster than lower powers.
Q65. An algorithm performs T(n) = 2T(n/2) + O(1). Complexity = ?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n²)
✅ Answer: A
Explanation: Equivalent to binary tree traversal → O(n).
Q66. log(n² + n) is asymptotically equal to:
A) Θ(log n)
B) Θ(n)
C) Θ(log² n)
D) Θ(n²)
✅ Answer: A
Explanation: n² term dominates → log(n² + n) ≈ 2 log n → Θ(log n).
Q67. For recurrence T(n) = 3T(n/4) + n, asymptotic complexity = ?
A) O(n log n)
B) O(n^(log₄3))
C) O(n²)
D) O(n)
✅ Answer: A
Explanation: n^(log₄3) ≈ n^0.79 < n → f(n)=n dominates → O(n).
Q68. Which algorithm has O(n log n) in worst case?
A) Merge Sort
B) Quick Sort
C) Bubble Sort
D) Insertion Sort
✅ Answer: A
Explanation: Merge Sort’s divide-and-conquer ensures O(n log n).
Q69. If T(n) = T(n−2) + n, complexity = ?
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
✅ Answer: A
Explanation: Linear summation with step 2 → O(n²).
Q70. The asymptotic growth of 5ⁿ compared to 2ⁿ is:
A) Faster
B) Slower
C) Same
D) Cannot determine
✅ Answer: A
Explanation: Higher base exponential grows faster.
Q71. The average-case complexity of linear search is:
A) O(n)
B) O(log n)
C) O(n²)
D) O(1)
✅ Answer: A
Explanation: On average, half elements checked.
Q72. Which function grows fastest asymptotically?
A) n³
B) n³ log n
C) n³ + 100
D) n³ log² n
✅ Answer: D
Explanation: Extra log² n factor dominates.
Q73. The asymptotic lower bound of comparison-based sorting is:
A) Ω(n²)
B) Ω(n log n)
C) Ω(log n)
D) Ω(n)
✅ Answer: B
Explanation: Derived from decision tree argument.
Q74. If f(n)=n log n and g(n)=n, which is true?
A) f(n)=O(g(n))
B) f(n)=Ω(g(n))
C) f(n)=Θ(g(n))
D) None
✅ Answer: B
Explanation: n log n grows faster → lower bound Ω(g(n)).
Q75. The recurrence T(n)=T(n/2)+√n gives:
A) O(√n log n)
B) O(n)
C) O(log n)
D) O(n log n)
✅ Answer: A
Explanation: Using recursion tree → O(√n log n).
Q76. The complexity of finding maximum in an unsorted array = ?
A) O(1)
B) O(n log n)
C) O(n)
D) O(log n)
✅ Answer: C
Explanation: Must scan all elements → O(n).
Q77. f(n)=2ⁿ and g(n)=nⁿ ⇒ which is true?
A) f=o(g)
B) f=Ω(g)
C) f=Θ(g)
D) f grows faster
✅ Answer: A
Explanation: nⁿ grows faster than 2ⁿ.
Q78. In Big-O notation, constants are:
A) Ignored
B) Doubled
C) Multiplied
D) None
✅ Answer: A
Explanation: Only dominant term matters asymptotically.
Q79. For T(n)=4T(n/2)+n, the time complexity is:
A) O(n²)
B) O(n log n)
C) O(n² log n)
D) O(n³)
✅ Answer: A
Explanation: log₂4=2 → O(n²).
Q80. log₂n! asymptotically equals:
A) Θ(n log n)
B) Θ(n²)
C) Θ(log n)
D) Θ(n)
✅ Answer: A
Explanation: Stirling approximation → log₂n! ≈ n log₂n.
Q81. If algorithm’s time T(n)=O(n³) and space S(n)=O(n²), what dominates asymptotically?
A) Time
B) Space
C) Both same
D) Cannot determine
✅ Answer: A
Explanation: n³ > n² asymptotically.
Q82. Function (n/2) log(n/2) = ?
A) Θ(n log n)
B) Θ(log n)
C) Θ(n)
D) Θ(n²)
✅ Answer: A
Explanation: Constants ignored → Θ(n log n).
Q83. T(n)=3T(n/2)+n² gives:
A) O(n²)
B) O(n² log n)
C) O(n³)
D) O(n^(log₂3))
✅ Answer: B
Explanation: f(n)=n² matches → O(n² log n).
Q84. Function n³/10 − n² + 7 grows as:
A) O(n³)
B) O(n²)
C) O(n)
D) Θ(1)
✅ Answer: A
Explanation: n³ dominates all lower powers.
Q85. log(log n) grows slower than:
A) log n
B) n
C) √n
D) All of these
✅ Answer: D
Explanation: Double log is slower than any of these.
Q86. If f(n)=O(n²) and g(n)=O(n³), then f(n)+g(n)=?
A) O(n³)
B) O(n²)
C) O(n⁵)
D) O(n⁶
)
✅ Answer: A
Explanation: Maximum dominates → O(max(n², n³)) = O(n³).
Q87. If T(n)=T(n−1)+T(n−2)+1, complexity is:
A) O(2ⁿ)
B) O(n²)
C) O(n log n)
D) O(log n)
✅ Answer: A
Explanation: Fibonacci-like recurrence → exponential.
Q88. For T(n)=T(n−1)+n, time complexity = ?
A) O(n²)
B) O(n log n)
C) O(n)
D) O(2ⁿ)
✅ Answer: A
Explanation: Summing linear series → O(n²).
Q89. Function n log n + n² log n = ?
A) Θ(n² log n)
B) Θ(n log n)
C) Θ(n²)
D) Θ(log n)
✅ Answer: A
Explanation: Dominant term n² log n.
Q90. log₂(n³) = ?
A) 3 log₂n
B) log₃n
C) n log₂3
D) log₂n + 3
✅ Answer: A
Explanation: log(aᵇ)=b log a → 3 log₂n.
Q91. The fastest asymptotic function:
A) n!
B) 2ⁿ
C) n³
D) n log n
✅ Answer: A
Explanation: Factorial > exponential > polynomial.
Q92. If T(n)=4T(n/2)+n³, complexity = ?
A) O(n³)
B) O(n² log n)
C) O(n⁴)
D) O(n³ log n)
✅ Answer: C
Explanation: log₂4=2 < 3 → f(n)=n³ dominates → O(n³).
Q93. Function (n log n)/(log log n) = ?
A) O(n log n)
B) Ω(n log n)
C) Θ(n log n)
D) o(n log n)
✅ Answer: D
Explanation: Denominator grows slowly → slightly smaller than n log n.
Q94. Binary tree traversal complexity:
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
✅ Answer: A
Explanation: Each node visited once.
Q95. If T(n)=2T(n−1)+1, complexity = ?
A) O(2ⁿ)
B) O(n²)
C) O(log n)
D) O(n)
✅ Answer: A
Explanation: Exponential recurrence → 2ⁿ growth.
Q96. f(n)=n²/log n grows slower than:
A) n²
B) n log n
C) n³
D) All of these
✅ Answer: A
Explanation: Division by log n reduces growth rate slightly.
Q97. The asymptotic complexity of heap sort = ?
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
✅ Answer: A
Explanation: Heap construction + n extract-min = O(n log n).
Q98. If f(n)=n² + 3n + 7, then f(n)=?
A) Θ(n²)
B) O(n³)
C) Θ(n)
D) Ω(n³)
✅ Answer: A
Explanation: Dominant term n².
Q99. If T(n)=T(n/2)+n/log n, complexity = ?
A) O(n)
B) O(n log n)
C) O(n log log n)
D) O(n²)
✅ Answer: A
Explanation: f(n) < n → O(n).
Q100. The average-case complexity of QuickSort = ?
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n)
✅ Answer: A
Explanation: Balanced partitions yield expected O(n log n).