Base Case: T(1) = 0;
T(n) = 1 + T(N/2)
plug = 1 + 1(1 + T(N/4))
chug = 2 + T(N/4)
plug = 2 + 1 (1 + T(N/8))
chug = 3 + T(N/8)
plug = 3 + 1 (1 + T(N/16))
chug = 4 + T(N/16)
pattern = i + T(N/2^i)
N/2^i = 1
2^i = N
i = log_2(N)
final equation :
log_(2)N + T(1)
Conlusion : O(log_N)
I have tried solving the question, but I'm not sure whether the method i used was correct. Plz review.