Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
| 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 |
- Option : B
- Explanation :
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
83. Which of the following sorting algorithms has the lowest worst-case complexity?
- Option : A
- Explanation : Merge sort has lowest worst – case complexity, i.e. O(n log n), whereas all remaining three has O(n2)
- Option : B
- Explanation : 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(n2 logn)
- Option : C
- Explanation : 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)
