Why does $T(\lg u)$ have the same complexity as $T(u)$?

Question

I have seen on this video (van Embde Boas Trees) at time 8:00 that:
$$T(\lg u) = T(\lg u/2) + \mathcal{O}(1) = \mathcal{O}(\lg \lg u)$$ and that $$T(u) = T(\sqrt{u}) + \mathcal{O}(1) = \mathcal{O}(\lg \lg u)$$ have the same complexity.

I don't see the connection on why these two recurrences have the same complexity.

Answer 1

Note that in the first recurrence $$ T(\lg(u)) = T\left(\frac{\lg (u)}2\right) + \mathcal O(1) = \mathcal O(\lg(\lg(u))) $$ you have $$ \frac{\lg(u)}{2} = \frac{1}{2} \lg(u) = \lg\left(u^{\frac 1 2}\right) = \lg(\sqrt{u}) $$ so you can rewrite it as $$ T(\lg(u)) = T(\lg(\sqrt{u})) + \mathcal O(1) = \mathcal O(\lg(\lg(u))). $$ Then letting $T'(z) = T(\lg z)$ you obtain $$ T'(u) = T'(\sqrt{u}) + \mathcal O(1) = \mathcal O(\lg(\lg(u))). $$

Answer 2

The first one, if you change variables to $x = \lg u$, reads $T(x) = T(x/2) + O(1)$ and assume $x=2^k$, you get $$ \begin{split} T(x) &= T(x/2) + O(1) \\ &= \left(T(x/2^2) + O(1)\right) + O(1)\\ &= T(x/2^2) + 2O(1) \\ &= T(x/2^3) + 3O(1) \\ & \ldots \\ &= T(x/2^k) + O(k) \\ &= T(1) + O(k) = O(k) \end{split} $$ since $x=2^k$ we have $k = \lg x$ and thus $T(x) = O(\lg x)$ or in the original variables, $T(\lg u) = O(\lg \lg u)$.

Can you use a similar argument for the second recurrence?