This set of Discrete Mathematics Multiple Choice s & Answers (MCQs) focuses on “Complexity of Algorithms”.

1. Which of the following case does not exist in complexity theory?

a) Best case

b) Worst case

c) Average case

d) Null case

View Answer

Explanation: 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^{2})

d) O(n log n)

View Answer

Explanation: 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^{2})

d) O(n log n)

View Answer

Explanation: 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^{2})

d) O(n log n)

View Answer

Explanation: 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^{2})

d) O(n log n)

View Answer

Explanation: The worst case complexity for Bubble sort is O(n

^{2})ans 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

View Answer

Explanation: 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^{2})

d) O(n log n)

View Answer

Explanation: 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^{n})

b) O(log n)

c) O(n^{2})

d) O(n log n)

View Answer

Explanation: Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2

^{n}. Now prove inductively that f(n) > = g(n).

9. The worst case occur 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 these

View Answer

Explanation: 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^{2})

d) O(n log n)

View Answer

Explanation: The worst case complexity of quick sort is O(n

^{2}).

**Sanfoundry Global Education & Learning Series – Discrete Mathematics**

To practice all areas of Discrete Mathematics, __here is complete set of 1000+ Multiple Choice Questions and Answers__.