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).
You must be logged in to post a comment.
- Option : B
- Explanation : The minimum number of comparison is logn.
You must be logged in to post a comment.
You must be logged in to post a comment.
- 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)
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : C
- Explanation : Both function preform same operation so result is same 1640 & 1640
You must be logged in to post a comment.
You must be logged in to post a comment.
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.
You must be logged in to post a comment.
You must be logged in to post a comment.
You must be logged in to post a comment.