Recurrence T(n)= T(n^1\2) + O(lg(lg(n)))
The solution suggests substituting
m = lg(n)
So the recurrence becomes
S(m)= S(m\2) + O(lg(lg(m)))
Then solving using iterative method for solvng recurrences.
How did the substitution above of m= lg(n) produce S(m)? In other words, why did it succeed in getting rid of n^1\2 ?
Thanks in advance.