Complexity of Algorithms - Discrete Mathematics Questions and Answers

This set of Discrete Mathematics Multiple Choice s & Answers (MCQs) focuses 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
View Answer

Answer: d
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²)
d) O(n log n)
View Answer

Answer: a
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²)
d) O(n log n)
View Answer

Answer: b
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²)
d) O(n log n)
View Answer

Answer: d
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²)
d) O(n log n)
View Answer

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

Answer: d
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²)
d) O(n log n)
View Answer

Answer: c
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ⁿ)
b) O(log n)
c) O(n²)
d) O(n log n)
View Answer

Answer: a
Explanation: 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
View Answer

Answer: b
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²)
d) O(n log n)
View Answer

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

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

« Prev - Discrete Mathematics Questions and Answers – Algorithms – Types

» Next - Discrete Mathematics Questions and Answers – Algorithms – Complexity-2

Related Posts:

Recommended Articles: