Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- Option : D
- Explanation : f(n) = 2n g(n) = n! ≅ nn h(n) = nlogn for larger value of n g(n) > f(n) > h(n) so we can conclude that f(n) = O(g(n)) or g(n) = Ω(f(n)) and h(n)= Of(n).
- Option : B
- Explanation : Recurrence relation for f1()is T (n) = 2T (n–1) + 3 T (n–2) After solving it would be Θ(1.6)n) so the largest value among the options is Θ(2n). f2() is simple loop executed n times. So Θ(n)
60. What is the number of swaps required to sort n elements using selection sort, in the worst case?
- Option : A
- Explanation : If there are n elements, then in worst case, total swaps will be (n-1) in selection sort. So the number of swaps is Θ(n). Alternately The selection sort is similar to bubble sort except it does not swap elements with every move. The sorting algorithm first finds the smallest element in the list and then puts it in to place in single swap. So n swap required for n elements.
