Write a recurrence that expresses the total number of additi

Write a recurrence that expresses the total number of additions performed by WHAT, then pick a convenient form of n and solve your recurrence. Prove that your solution is correct.

Solution

Answer:

It divides the equation into 2 parts : low-mid and mid+1-high .So it would be T(n/2)+T(n/2) Which gives 2T(n/2).. There is 1 addition in the final answer, so we have to add the 1 too.. because we have to add the number of additions. So it becomes :

2T(n/2)+1

Now , use the Master\'s theorm

Here a = 2 , b = 2 , c = 0

log2 base 2 = 1 , c < loga base b , therefore , T(n) = theta(n^log2 base 2 ) = theta(n)

Therefore , T(n) = theta(n).