Consider the following recurrence relation:
$$T(n) = 2T(\lceil{\sqrt{n}\rceil}) + 1 \text{ if } n >2$$
$$T(n) = n \text{ if } n \leq 2$$
I can see intuitively that
$$T(n) = O(\log{n})$$
because there are $O(\log\log{n})$ levels to the recursion and the value is doubled at each level.
Is there a nice formal proof of this result?
$$ T(n) = 2T(\lceil{\sqrt{n}\rceil}) + 1 \text{ if } n >2 $$
is equivalent to
$$ T(\lceil n\rceil) = 2T(\lceil{\sqrt{n}\rceil}) + 1 \text{ if } n >2 $$
so calling
$T'(n) = T(\lceil n\rceil)$ we have
$$ T'(e^{\ln n}) = 2T'(e^{\frac 12\ln n})+1 $$
and calling $T''(z) = T'(e^z)$ we have
$$ T''(\ln n) = 2 T''(\frac 12\ln n) + 1 $$
or
$$ T''(2^{\log_2(\ln n)}) = 2T''(2^{\log_2(\ln n)-1})+1 $$
and now with $T'''(u) = T''(2^u)$ with $u = \log_2(\ln n)$
$$ T'''(u) = 2T'''(u-1)+1 $$
This is a linear recurrence equation with solution
$$ T'''(u) = C_1 2^{u-1}+2^u-1 $$
The return to $T(n)$ is left to the reader