# Math Help - Algorithm Analysis

1. ## Algorithm Analysis

This is about an Merge Sort computer algorithm.
Firstly here's the full thing.

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

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

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

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

$
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
$

$
= 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.

2. Originally Posted by alyosha2
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?
In when n=1 there is nothing to do $T(1)=0$ , though you might be happier hand working the case $n=2$ to find the value of $T(2).$

For the rest of your post could you please reorganise it so that it is easier to see what your questions are and please clean up you LaTeX.

CB

3. Originally Posted by CaptainBlack
In when n=1 there is nothing to do $T(1)=0$ , though you might be happier hand working the case $n=2$ to find the value of $T(2).$

For the rest of your post could you please reorganise it so that it is easier to see what your questions are and please clean up you LaTeX.

CB
Cleaned up LaTeX

$
2^{log\;n-1}T(\frac{n}{2^{log\;n-1}}) + 2^{log\;n-1} + ... + 2n - 2 + 2n - 1
$

$
= n + 2n \log{n} - 2^{log\;n-1} + 1 = 2n \log{n} + 1 = O(n \log{n})
$

Ok, what I'm trying to get at is understadning each step of the expresion as it relates to the merge sort algorithm.

Merge sort takes an array of n number of inputs and then keeps dividing them untill they reach single inputs it then arranges them into sorted arrays by first adding single inputs to make arrays of two then two to make arrays of four etc. until you have one sorted array.

so if T(n) represent the time complexity of the algorithm then

$
T(\frac{n}{2}) + T(\frac{n}{2}) + mergetime
$

mergetime is 2n - 1

there a much better(more mathmatical) description on wikipedia

Merge sort - Wikipedia, the free encyclopedia

the point where my understading begins to slip is on the second line. I can see that the 2squared before the T and in the denominator result from multiplying out the brackets and the 2n also. But at this point I can't see what part of the algorithm 2n - 2 is representing. I can't make the link.

This then becomes represented as - 2 to the power of k in the next part and then log of n in the next part. But I think I'll understand these when I understand where the original - 2 comes from(or rather waht it represents).

And lastly how do you end up with n in the begining of the first part of the last line as well as the + 1 at the end.

I hope that's clear enough, as I'm sure you can tell I'm a bit confused.

Thanks.

4. No one has any ideas?

Is the question too vauge or confused?

I'd appreciate help with this if anyone can.

Thanks.