I am confused with the below explanation in one of the google searches for merge sort
T(n) = 2T(n/2) + (n-1) This left side equation, if you solve, will resolve to n*log(n)
Here 2T(n/2) is right, because each time we are breaking into the n elements array, into 2 parts...and splitting them further, until we reach a single element array.
In the merge part, at the most, we compare n elements at the worst case.
But, as shown in the above equation, it n-1. Not able to understand, why it is n-1.