Question-37

What is recurrence and time complexity for worst case of Merge Sort ?

• Recurrence is \(T(n) = 2T(n/2) + O(n)\) and time complexity is \(O(n^2)\)
• Recurrence is \(T(n) = T(n/2) + O(n)\) and time complexity is \(O(n^2)\)
• Recurrence is \(T(n) = 2T(n/2) + O(n)\) and time complexity is \(O(n\log n)\)
• Recurrence is \(T(n) = 2T(n/2) + O(1)\) and time complexity is \(O(n\log n)\)

Answer

• Recurrence is \(T(n) = 2T(n/2) + O(n)\) and time complexity is \(O(n^2)\)
• Recurrence is \(T(n) = T(n/2) + O(n)\) and time complexity is \(O(n^2)\)
• Recurrence is \(T(n) = 2T(n/2) + O(n)\) and time complexity is \(O(n\log n)\)
• Recurrence is \(T(n) = 2T(n/2) + O(1)\) and time complexity is \(O(n\log n)\)