educative.io

Educative

Mistake in recurrence equation for merge sort

T(n)=Costtodivideinto2unsortedarrays+2∗T(
2
n

)+Costtomerge2sortedarrayswhenn>1

IIUC it should be T(n)=2T(n/2) + n

Hi @manny1,

According to the explanation of this lesson, this is the time complexity of 1 last sub-array. It says the T(n) = O(1) when n = 1. In merge sort, we divide the array until the element is no more dividable, which means the last subarray will have only 1 element. So the time complexity of each subarray of element 1 will be constant.

I hope you got the point. If you still have any queries, please ask!
Thanks,