Register

GO Classes DPP | Algorithms | Quicksort,Mergesort

276 views
2 2 votes

Which of the following statements is/are not correct?
(Here $o, \omega$ represents small-oh and small-omega, respectively.)

  1. The average-case time complexity of quicksort $=\omega$ (the average case time complexity of mergesort)
     
  2. The best-case time complexity of quicksort = o(the best-case time complexity of mergesort)
     
  3. The best-case behaviour occurs for quicksort when the partition splits the array of size $n$ into $n / 2:(n / 2)-1$
     
  4. Quicksort is a stable algorithm

2 Answers

0 0 votes

The average and best-case time complexity of both algorithms is $\Theta$ (nlogn)

Quicksort is not stable

• reshown by
0 0 votes

\(f(n) = o(g(n))\) means \(f(n)\) grows strictly slower than \(g(n)\).
\(f(n) = \omega(g(n))\) means \(f(n)\) grows strictly faster than \(g(n)\).

Statement A: INCORRECT
Average-case of Quicksort = \(\Theta(n \log n)\)
Average-case of Mergesort = \(\Theta(n \log n)\)
Since both algorithms have the exact same growth rate in the average case, Quicksort cannot grow strictly faster (\(\omega \)) than Mergesort. They are asymptotically equal (\(\Theta \)).


Statement B: INCORRECT
Best-case of Quicksort = \(\Theta(n \log n)\)
Best-case of Mergesort = \(\Theta(n \log n)\)
Since both are \(\Theta(n \log n)\) in their best case, Quicksort cannot grow strictly slower (\(o\)) than Mergesort.


Statement D: INCORRECT
Quicksort is unstable by default.


 

Voting & Accepting an answer helps improve the community
Answer:
← Previous · A testseries questio...Next → · GO Classes DPP | Alg...
← Previous in category · Test SeriesNext in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

1 1 vote
3 3 answers
390
390 views
GO Classes asked Aug 28, 2025
390 views
GO Classes DPP | Algorithms | Quicksort
A machine needs a maximum of $200$ seconds to sort $1000$ elements by Quick sort. The maximum time needed (in seconds) to sort $200$ elements will be approximately ______...
3 3 votes
3 3 answers
352
352 views
GO Classes asked Aug 28, 2025
352 views
GO Classes DPP | Algorithms | Searching
You are given an $n \times n$ matrix where each row and each column is sorted in ascending order. You need to search for a target element "x" in the matrix.What is the be...
2 2 votes
1 1 answer
251
251 views
GO Classes asked Aug 28, 2025
251 views
GO Classes DPP | Algorithms | Binary search
A monkey is given $n$ piles of bananas, where the 'ith' pile has nums[i] bananas (nums is an array of size n ). An integer h represents the total time in hours to eat all...
1 1 vote
3 3 answers
282
282 views
GO Classes asked Aug 28, 2025
282 views
GO Classes DPP | Algorithms | Binary search
Alice has two sorted arrays $\mathrm{A}[1, \ldots, \mathrm{n}], \mathrm{B}[1, \ldots, \mathrm{n}+1]$. She knows that A is composed of distinct positive numbers, and B is ...