T(n)=Costtodivideinto2unsortedarrays+2∗T(
2
n
)+Costtomerge2sortedarrayswhenn>1
IIUC it should be T(n)=2T(n/2) + n
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,