change of variables in recurrences

Some recurrences refuse to fit the divide-and-conquer mould because the size shrinks in a strange way — by taking a square root, say, rather than dividing by a constant. The trick is to rename the variable so the recurrence turns into a familiar shape you already know how to solve, solve that, then translate back.

Take the classic T(n) = T(sqrt(n)) + 1. Dividing by sqrt is unlike anything the Master Theorem expects. Let m = log n (equivalently n = 2^m). Then sqrt(n) = n^(1/2) = 2^(m/2), so its log is m/2. Define S(m) = T(2^m) = T(n). The recurrence becomes S(m) = S(m/2) + 1 — and that we recognise instantly: by the Master Theorem (a=1, b=2, f=Theta(1)) it is S(m) = Theta(log m). Now translate back: T(n) = S(m) = Theta(log m) = Theta(log log n). The square-root shrink became an ordinary halving once we worked in the exponent.

Change of variables is the standard escape hatch for recurrences with sqrt(n), n^(1/k), or other non-linear size reductions — the move is almost always 'take logs to turn multiplicative shrinking into additive/halving shrinking'. The honest caveats: you must transform the base case too (when n is small, what is m?), and you should re-examine whether floors/ceilings introduced by sqrt of a non-perfect-square cause trouble (for asymptotics they typically do not). It is a reformulation, not a new theorem: all the work is in finding the right substitution so a known method applies.