Can someone help me figure out the big-O for the recurrence relation $T(n) = T(n^{1/2}) + 1$?
I didn't think the master theorem would work since it requires $T(n) = T(n/b)$... to have $b$ as a constant. I was wondering if anyone could shed some light on a method to approach this problem? (not looking for a solution)
First comment: the recurrence relation $T(n)=T(\sqrt{n})+1$ does not properly (ie completely and uniquely) define $T$ (e.g. what's $T(p)$ for $p$ prime ?).
A solution for that could be to use $T(n)=T(\lfloor n^{\frac 12}\rfloor)$.
Then, set $\phi_k(n)=k^{(2^n)}$. Clearly $\phi_k(n)^{1/2}=\phi_k(n-1)$, so $T(\phi_k(n))=T(\phi_k(n-1))+1$, which yields $T(\phi_k(n))=T(k)+n$.
Note $\log^{[2]} = \log_2 \circ \log_2$, you easily get $\phi_k(n)=p \Leftrightarrow n = \log^{[2]} p - \log^{[2]}k$.
So, if $p$ is of the form $p=k^{2^n}$, $$T(p)=\big(T(k)-\log^{[2]}k\big)+\log^{[2]} p \sim \log^{[2]} p\quad\quad(X)$$
Actually this is true for all $p$ as soon as your $T$ is completely defined in any "sensible" way.
(But note that you could for instance define $T(p)=p$ for $p$ not of the form $\phi_k(n)$, and complete with your recurrence relation, and ($X$) would no longer be true in general).