250+ TOP MCQs on Algorithms – Complexity and Answers

Discrete Mathematics Multiple Choice s on “Algorithms – Complexity-1”.

1. Which of the following case does not exist in complexity theory?
a) Best case
b) Worst case
c) Average case
d) Null case

Answer: d
Clarification: Null case does not exist in complexity Theory.

2. The complexity of linear search algorithm is _________
a) O(n)
b) O(log n)
c) O(n²)
d) O(n log n)

Answer: a
Clarification: The worst case complexity of linear search is O(n).

3. The complexity of Binary search algorithm is _________
a) O(n)
b) O(log)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: The compexity of binary search is O(logn).

4. The complexity of merge sort algorithm is _________
a) O(n)
b) O(log n)
c) O(n²)
d) O(n log n)

Answer: d
Clarification: The worst case complexity for merge sort is O(nlogn).

5. The complexity of Bubble sort algorithm is _________
a) O(n)
b) O(log n)
c) O(n²)
d) O(n log n)

Answer: c
Clarification: The worst case complexity for Bubble sort is O(n²) and best case is O(n).

6. The Worst case occur in linear search algorithm when _________
a) Item is somewhere in the middle of the array
b) Item is not in the array at all
c) Item is the last element in the array
d) Item is the last element in the array or is not there at all

Answer: d
Clarification: The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.

7. The worst case complexity for insertion sort is _________
a) O(n)
b) O(log n)
c) O(n²)
d) O(n log n)

Answer: c
Clarification: In worst case nth comparison are required to insert the nth element into correct position.

8. The complexity of Fibonacci series is _________
a) O(2ⁿ)
b) O(log n)
c) O(n²)
d) O(n log n)

Answer: a
Clarification: Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2ⁿ. Now prove inductively that f(n) > = g(n).

9. The worst case occurs in quick sort when _________
a) Pivot is the median of the array
b) Pivot is the smallest element
c) Pivot is the middle element
d) None of the mentioned

Answer: b
Clarification: This happens when the pivot is the smallest (or the largest) element. Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.

10. The worst case complexity of quick sort is _________
a) O(n)
b) O(log n)
c) O(n²)
d) O(n log n)

Answer: c
Clarification: The worst case complexity of quick sort is O(n²).