Number of comparisions


#1

Can someone explain how they arrived to the number of comparisons as 3n/2-2? I am getting the number as 3n-2 on solving the recurrence relation.


#2

Take the base case as T(2) = 1. So when solving the recurrence, put (n/2^k) = 2.
T(n) = 2^k * T(n/2^k) + 2^(k+1) - 2
Put n/2^k = 2
T(n) = 2^k.T(2) + 2^(k+1) - 2
T(n) = 2^k + 2^(k+1) - 2
T(n) = 3.2^k - 2
T(n) = 3n/2 - 2 (since 2^k = n/2)