I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution
I don't understand the transition in (1). how did we conclude that T(m) = T(m/2) + 1 from the previous step that m is in the power?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
It obviously is not correct. To fix it, define $S(m)=T(2^m)$, and then we would have $S(m)=S(m/2)+1$. Now, continue with the proof replacing everywhere $T(m)$ with $S(m)$. After you solve what $S(m)$ is, substitute $m=\log(n)$ in the solution to get what $T(n)=T(2^m)=S(m)$ is.