Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
101. Which one the following in place sorting algorithms needs the minimum number of swaps?
- Option : C
- Explanation : Minimum no of swap for selection sort is O when array is already sorted and maximum swap is Q(n).
- Option : C
- Explanation : Time complexity of radix sort is = O(nd) Where n = keys, d = maximum digit in keys. = d = log (nk) O(nd) = O(n * k logn) = k × O (nlogn) = O(nlogn)
103. The number of elements that can be stored in Θ(log n) time using heap sort is
- Option : C
- Explanation : Let the number of element is “K”, they can be
sorted in Θ(k log k) time.
We try the options in decreasing order of complexity since, we need a tight band i.e. Θ
So if K ∈ Θ(log n) time required for loop sort is.
Θ(k log k) i.e.
Θ(log n x log log n), But this is not in Θ(log n)
- Option : A
- Explanation : It input is in either ascending order or in descending order both are worst case of quick sort Algorithms.
- Option : C
- Explanation : If Input is either in ascending order or in descending order both are worst case of quick sort algorithm
