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

101 Which one the following in place sorting algorithms needs the minimum number of swaps?

Minimum no of swap for selection sort is O when array is already sorted and maximum swap is Q(n).

102 If we use Radix Sort to sort n integers in the range (n^k/12, n^k], for some k > 0 which is independent of n, the time taken would be

Time complexity of radix sort is = O(nd)
Where n = keys, d = maximum digit in keys.
= d = log (n^k)
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

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)

104 Let P be a quicksort program to sort numbers in ascending order. Let t₁ and t₂ be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of the following holds?

It input is in either ascending order or in descending order both are worst case of quick sort Algorithms.

105 Quicksort is run on two inputs shown below to sort in ascending order
(i) 1, 2, 3 ............. n
(ii) n, n–1,n–2, ..., 2, 1
Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

If Input is either in ascending order or in descending order both are worst case of quick sort algorithm