This is about an Merge Sort computer algorithm.

Firstly here's the full thing.

$\displaystyle

T(n) = 2T(\frac{n}{2}) + 2n - 1 = 2(2T(\frac{n}{4}) + 2\frac{n}{2} - 1 ) + 2n - 1

$

$\displaystyle

= 2^2 T(\frac{n}{2^2}) + 2n - 2 + 2n - 1

$

$\displaystyle

=2^kT(\frac{n}{2^k}) + 2n - 2^k ... 2n - 2 + 2n - 1

$

couldn't figure out how to get log as an exponent

$\displaystyle

2(to the log of n)T(\frac{n}{2(to the log of n)} + 2(to the log of n - 1) + ... + 2n - 2 + 2n - 1

$

$\displaystyle

= n + 2n \log{n} - 2(to the log of n) + 1 = 2n \log{n} + 1 = O(n \log{n})

$

I asked a question about this before and got a good answer that made me realise that what was going on was recursion. Now, to my understanding all recusion needs a base case. In this instance I'm thinking that this would be T(1) as this would mean that there would be no sorting to do. Does this mean that T(1) = 1? as in the last 3rd to last part where 2 to the log on n X T(n / 2 to the log of n) is reduced to n?

Also for each level of recursion that you go down I can understand that you would have another 2n - 1 (where n is the reduced input) but I'm having a hard time trying to see how this works as giving the 2n - 2 to log n -1 ... .

And lastly, and I'm quite sure this is linked to the above question, where does the + 1 come from in the last two but one parts?

Thanks.