MCQS
1. Which of the following is not an asymptotic notation?
A) Big-O (O)
B) Theta (Θ)
C) Sigma (Σ)
D) Omega (Ω)
Answer: C
2. What does the Big-O notation represent?
A) Best-case complexity
B) Average-case complexity
C) Worst-case complexity
D) Space complexity
Answer: C
3. If f(n) = O(g(n)) what does it imply?
A) f(n) grows faster than g(n)
B) f(n) grows slower than or at the same rate as g(n)
C) f(n)is always less than g(n)
D) None of the above
Answer: B
4. Which of the following best describes the reflexive property of
asymptotic notation?
A) f(n) = O(g(n)) and g(n) = O(h(n)) lead to f(n) = O(h(n)).
B) Any function f(n) is always O(f(n).
C) If f(n) = O(g(n)), then g(n) = O(f(n)).
D) f(n) and g(n) must grow at the same rate for the property to hold.
Answer: B
5. The transitivity property of asymptotic notations implies:
A) f(n) = O(g(n)) and g(n) = O(h(n)) lead to f(n) = O(h(n))
B) f(n) = O(g(n)) + h(n)
C) f(n) = O(k ⋅ g(n))
D) None of the above
Answer: A
6. What is the time complexity of the binary search algorithm?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
Answer: C
7. Which recurrence relation represents binary search?
A) T(n) = T(n/2) + O(1)
B) T(n) = 2T(n/2) + O(1)
C) T(n) = T(n/4) + O(n)
D) T(n) = 3T(n/4) + O(n2)
Answer: A
8. Which of the following recurrence relations can be solved using the
substitution method?
A) T(n) = T(n/2) + c
B) T(n) = 2T(n/2) + n
C) Both A and B
D) None of the above
Answer: C
9. If T(n) = T(n/2) + c, what is the time complexity?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
Answer: B
10. If T(n) = 2T(n/2) + n, what is the time complexity?
A) O(n log n)
B) O(log n)
C) O(n^2)
D) O(n)
Answer: A
11. According to the Master Theorem, what is the complexity of T(n) =
T(n/2) + c?
A) O(log n)
B) O(n log n)
C) O(n^2)
D) O(n)
Answer: A
12. What is the time complexity of T(n) = 8T(n/2) + n?
A) O(n log n)
B) O(n^3)
C) O(n^2)
D) O(n^2 log n)
Answer: B
13. The recurrence T(n) = 3T(n/4) + cn represents:
A) Divide and Conquer
B) Dynamic Programming
C) Brute Force
D) None of the above
Answer: A
14. For T(n) = 3T(n/4) + cn, the time complexity is:
A) O(n^3)
B) O(n^2 log n)
C) O(n^2)
D) O(n log n)
Answer: C
15. Divide and Conquer algorithms work by:
A) Dividing the problem into smaller subproblems, solving them independently,
and combining the results
B) Solving the problem in one go without division
C) Dividing the problem into unrelated subproblems
D) Combining the problem into one step
Answer: A
16. Which of the following is not a Divide and Conquer algorithm?
A) Merge Sort
B) Binary Search
C) Bubble Sort
D) Quick Sort
Answer: C
17. What is the worst-case time complexity of Quick Sort?
A) O(n log n)
B) O(log n)
C) O(n^2)
D) O(n)
Answer: C
18. In Quick Sort, the partition step divides the array into:
A) Equal-sized subarrays
B) Subarrays based on a pivot element
C) Random subarrays
D) None of the above
Answer: B
19. The average time complexity of Quick Sort is:
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
Answer: A
20. What happens in the partition step of Quick Sort?
A) The array is sorted in one step
B) A pivot element is chosen, and elements are rearranged such that smaller
elements are on one side and larger ones on the other
C) The array is divided into equal halves
D) None of the above
Answer: B
