T(n) = T( √n) + log2 n _____________ Eqn 1
Let's take n = 2m , taking log both side.
log2 n = m log22 put in Eqn 1.
T(2m) = T(2m/2) + log2 2m _____________ Eqn 2
[ ∵ logb bn = n ] using this we can rewrite Eqn 2 as :
T(2m) = T(2m/2) + m
or
S(m) = S(m/2) +m
solve using MT we get, S(m) = O(m)
change the value of m to log2n.
so TC is log2n