I have a doubt related to the Mathematical proof of merge sort's algorithm. As i see only the proof is Mathematical but the problem is related to Algorithm.
Time complexity of merge sort in worst case, T(n) = 2T(n/2) + n-1
=> T(n) = n-1 + 2T(n/2) // recursive part always at end to keep it simpler
By plug & chug method:
T(n) = n-1 + 2[n/2-1 + 2T(n/4) ] //plug
= n-1 + n-2 + 4T(n/4) //chug
= n-1 + n-2 + 4[n/4 -1 + 2T(n/8)] //plug
= n-1 + n-2 + n-3 + ....... + n- 2^i-1 + 2^i T(n/2^i) //rounding off
now i have doubt in this step why did he take i as log(n-1)? which gives us an answer:
=nlogn -n+1
As the size of the problem n decreases, half at a time, n becomes the size of base case problem which can be solved in constant time.
In this case n=1 is the base case as T(1) is known to be of order O(1).
In your expansion, the number i is how many times n has been halved.
Now the question is: when n becomes 1 where the recursion stops, what is the value i at that point?
That is, how many times n can be divided by 2 until it becomes 1?
The answer is log_2(n)
So the 'plug and chug' expansion stops at value i = log_2(n)