Question:
What is the recurrence relation for the Merge Sort algorithm on an input of size \(n\), and what is its space complexity?
\(n\) आकार के इनपुट पर मर्ज सॉर्ट एल्गोरिदम के लिए पुनरावृत्ति संबंध और इसकी स्थान जटिलता क्या है?
Options:
- \(T(n) = 2T(n/2) + \Theta(n)\) with space complexity \(O(n)\)
- \(T(n) = T(n-1) + \Theta(n)\) with space complexity \(O(1)\)
- \(T(n) = 2T(n/2) + \Theta(1)\) with space complexity \(O(n \log n)\)
- \(T(n) = 3T(n/2) + \Theta(n)\) with space complexity \(O(\log n)\)
- \(T(n) = 2T(n/2) + \Theta(n)\), स्थान जटिलता: \(O(n)\)
- \(T(n) = T(n-1) + \Theta(n)\), स्थान जटिलता: \(O(1)\)
- \(T(n) = 2T(n/2) + \Theta(1)\), स्थान जटिलता: \(O(n \log n)\)
- \(T(n) = 3T(n/2) + \Theta(n)\), स्थान जटिलता: \(O(\log n)\)
Correct Answer: a)
Explanation:
Merge Sort splits the array in halves (\(2T(n/2)\)) and merges them in linear time (\(\Theta(n)\)). It requires an auxiliary array of size \(n\) to merge, so space complexity is \(O(n)\).
मर्ज सॉर्ट दो हिस्सों को सॉर्ट करके \(O(n)\) में मिलाता है (\(T(n) = 2T(n/2) + O(n)\)) और इसके लिए \(O(n)\) सहायक मेमोरी की आवश्यकता होती है।