This is about an Merge Sort computer algorithm.
Firstly here's the full thing.
couldn't figure out how to get log as an exponent
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.
Cleaned up LaTeX
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
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.