T(n) = T(n/2) + 2
T(n/2) = T(n/4) + 2
T(n/4) = T(n/8) + 2
...
=> T(n) = T(n/2) + 2
= (T(n/4) + 2) + 2 = T(n/4) + 2*2
= (T(n/8) + 2) + 2*2 = T(n/8) + 2*3
= T(n/k) + 2*log k
Base condition: T(1) = 1
n/k = 1
=> k = n
Thus T(n) = T(n/n) + 2* log n
= 1 + 2 log n