Question:
What is the worst-case time complexity of QuickSort when the pivot element is always chosen as the median of the array using a linear-time median-finding algorithm?
जब क्विकसॉर्ट में एक रैखिक-समय माध्यिका-खोज एल्गोरिदम का उपयोग करके पिवट तत्व को हमेशा ऐरे की माध्यिका के रूप में चुना जाता है, तो इसकी सबसे खराब स्थिति की समय जटिलता क्या होगी?
Options:
- \(O(n \log n)\)
- \(O(n^2)\)
- \(O(n)\)
- \(O(n \log^2 n)\)
- \(O(n \log n)\)
- \(O(n^2)\)
- \(O(n)\)
- \(O(n \log^2 n)\)
Correct Answer: a)
Explanation:
Choosing the exact median as pivot guarantees a balanced partition of size \(n/2\) on each step. The recurrence becomes \(T(n) = 2T(n/2) + O(n)\), which by Master Theorem solves to \(O(n \log n)\) even in the worst case.
यदि पिवट हमेशा माध्यिका हो तो ऐरे हमेशा दो समान भागों (n/2) में विभाजित होता है, जिससे सबसे खराब स्थिति में भी समय जटिलता \(O(n \log n)\) हो जाती है।