Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

81 Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

List-I (Recursive Algorithm)		List-II (Recurrence Relation)
P.	Binary search	I.	T(n) = T(n - k) + T(k) + cn
Q.	Merge sort	II.	T(n) = 2T(n - 1) + 1
R.	Quick sort	III.	T(n) = 2T(n/2) + cn
S.	Tower of Hanoi	IV.	T(n) = T(n/2) + 1

Which of the following is the correct match between the algorithms and their recurrence relations?

Codes:

	P	Q	R	S
(a)	II	III	IV	I
(b)	IV	III	I	II
(c)	III	II	IV	I
(d)	IV	II	I	III

Algorithm	Recurrence Relation
P. Binary Search	IV. T (n) = T (n/2) + 1
Q. Merge Sort	III. T (n) = 2T (n/2) + cn
R. Quick Sort	I. T (n) = T (n-k) + T (K)
S. Tower of Hanoi	II T (n) = 2T (n-1)+1

82 Suppose there are log n sorted lists of n/log n elements each. The time complexity of producing a sorted list of all these elements is:
(Hint: Use a heap data structure)

x = n/logn
y = logn
we get O(n/logn * logn * log logn)
So O (n log logn)

83 Which of the following sorting algorithms has the lowest worst-case complexity?

Merge sort has lowest worst – case complexity, i.e. O(n log n), whereas all remaining three has O(n²)

84 A list of n strings, each of length n, is sorted into lexicographic order using the merge sort algorithm. The worst case running time of this computation is

Recurrence relation for merge sort
T (n) = 2 T (n/2) + n
So T (n) = O(n logn)
but instead of integers whose comparison take O(1) time, we are given n strings so to compare strings we need O(n) time hence complexity is Q(n² logn)

85 Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

Given: n numbers
To find: Tightest upper bound on number of swaps required to sort n numbers using selection sort.
Analysis: In selection sort, in the unsorted part of the array, we find the minimum element and swap it with the value placed at the index where the unsorted array starts.
Hence, for each element to put it in its sorted position, we will do some swaps. In each iteration, when we find the minimum and place it in its sorted position, we do only one swap. There are n such iterations, since maximum number of positions to sort is n.
Hence, there are n.O(1) swaps
⇒ O(n) swaps.
∴ The solution is (C)