• Register
    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 580

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
  • Questions
    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 580
  • Unanswered
    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 580
  • Tags
    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 580
  • Categories
    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 580
  • Users
    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 580
  • Exams Taken
    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 580
  • Exam List
    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 580

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

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

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

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

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

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
+2 votes

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) \Theta(nlogn)

(C) \Omega(n)

(D) \Theta(n^2)

asked Aug 29, 2020 by gbeditor-2 (72,840 points)
reshown Sep 10, 2020 by gbeditor-2

2 Answers

0 votes
 
Best answer

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 deepak-gatebook (226,240 points)
0 votes

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 tsshashankrustagi (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)
Answer:

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

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

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
...