Solve the recurrence $T(n) = 3T(\sqrt n) + \log n$. by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Let us assume $n = 10^m$, $m = \log n$. Hence, the recurrence takes the form

$T(10^m) = 3T(10^{m/2}) + m$.

Now, assuming $S(m) = T(10^m)$, the recurrence takes the form

$S(m) = 3S(m/2) + m$.

Now, I don’t know how is it possible for anyone who doesn’t know Master Theorem yet or has no clue about the form of the asymptotic bound can even start to solve this by substitution.

Anyway, it is easy to solve this by substitution once you know the form of the asymptotic tight bound. Just follow the previous examples.