Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DSA - Grand Test -Q18

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Consider a variation of merge sort algorithm named M' algorithm which first checks whether the given array is already sorted or reverse sorted or not. And if the given array is already sorted then it does nothing and returns the array. If the array is reverse sorted then it performs the quick sort algorithm on it and sorts the array and returns it. If the array is neither sorted nor reverse sorted then it performs the conventional merge sort algorithm and sorts the array and returns it. The time complexity of this algorithm is

(A) O(nlogn)

(B) $\dpi{100} \Theta(nlogn)$

(C) $\dpi{100} \Omega(n)$

(D) $\dpi{100} \Theta(n^2)$

reshown Sep 10, 2020

If the given array is sorted  then Θ(n) --- best case

If the given array is reverse sorted, QS will run and take Θ($n^{2}$) -----worst case

If it is neither sorted nor reverse sorted, it will take   Θ(nlogn) time -----average case

Ω(n) which is correct.

Θ(n^2) is not correct because it will mean that in all cases we are taking n^2 time.

Theta(nlogn) is Not correct answer because it will mean that in all cases we are taking nlogn time.
Possible answers are : Omega(n) , O(n^2)

answered Sep 26, 2020 by (226,240 points)

If the given array is sorted Ω(n) --- best case

If the given array is reverse sorted QS will run and take O($n^{2}$) -----worst case

If it is neither sorted nor reverse sorted, it will take   Θ(nlogn) time -----average case

Total time : Θ(nlogn) only.

In the options Best case time is given.

Ω(n) which is correct.

Θ(nlogn) is also a valid answer. But it is not given in the options.

answered Sep 26, 2020 by (11,240 points)
Theta(nlogn) is Not correct answer because it will mean that in all cases we are taking nlogn time.
Possible answers are : Omega(n) , O(n^2)