GATE 2024 algorithm Rank Booster Quiz 22

What is recurrence relation for the worst case of Quicksort and time complexity in the Worst case of Quick Sort respectively?

In the Worst case, in Selection Sort, the total number of moves represented in order of______?

Suppose we modify merge sort in the following two ways :
• We split the input into three equal segments, recursively sort each segment and then do a three way merge of the three sorted segments to obtain a fully sorted output.
(Let us call this as 3 way merge sort)
• We split the input into two unequal segments, first segment contains only one element and other segment is biased to the right side, recursively sort each segment and then do a two way merge of the two sorted segments to obtain a fully sorted output.
(Let us call this as biased merge sort)
What can we say about the asymptotic worst case complexity of merge sort , 3 way merge sort and biased merge sort ?

Solve the following Recurrence Relation:

Consider the following recurrence relation

T(n) = 6 T(n/3) + n²log n

Time complexity of above relation is

Give the correct matching for the following pairs when best cases are assumed for algorithms:

In Quicksort, which of the following is true?

i) Ideal for sorted array

ii) Works best when input is not almost sorted.

iii) worst case is O(n²)

iv) Better than insertion sort for every type of input.