How to derive the complexity of a Merge Sort . I know it is O(nlogn).
But how does this Log n is derived . On Many posts around the web , its mentioned , "Similar to Binary search"
But ideally to verify the time complexity , i counted the total number of function calls .
For eg : int arr[]={5,1,3,2}
then level 0 --- > f(arr(4)) (2^0)
level 1--- > f(arr(2)) , f(arr(2)) ( 2 ^1 )
level 2--- > f(arr(1) , f(arr(1) , f(arr(1) ,f(arr(1) . (2^2)
ideally total time spent should be = 1 + 2 + 4 = 7 , which means 2^(2+1) -1 = 7
Is this the right deduction ? if yes , how to generalise this time complexity in terms of size of the array ? and also why it should be log n ??
ALso, can anybody share a good editorial where i can learn the time complexity evaluation techniques .
Please help !