Question

T(n) =T(n^(1/2))+1

Comments

Substitute n = 2^m ...then subsitute T(2^m) = S(m)..then apply masters theorem.

Answer 1

T(n) = T(sqrt n) +1

let n = 2^m                   .........................(1)

T(2^m) = T(2^m/2) + 1

assume T(2^m) = S(m)

so S(m) = S(m/2) + 1

apply master theorem

S(m) = theeta (log m)

from (1)

so T(n) = theeta (log log n)