I am trying to perform asymptotic analysis on the following function in terms of Big O:
$T(n) = T(n^{\frac{1}{2}}) + n$
$T(1) = 1$
I have found that: $T(n) = T(1) + \sum_{k = 1}^{log(log(n)) -1} n^{\frac{1}{2^{k-1}}}$
I have also found the following inequality: $n\leq 1 + \sum_{k = 1}^{log(log(n)) -1} n^{\frac{1}{2^{k-1}}}$
However, I am having difficulty finding the upper limit. I know that the overall bound is $\Theta (n)$, and the upper limit must also be $O(n)$. Can anyone help me with this problem?
(Note: in $T(n) = T(n^{\frac{1}{2}}) + n$, I assume we take the value of $T$ on the integer part of $n^{\frac{1}{2}}$; so $T(n) = T(\lfloor{n^{\frac{1}{2}}}\rfloor) + n$ would be clearer).
$T(n) = T(1) + \sum_{k = 1}^{\log(\log(n)) -1} n^{\frac{1}{2^{k-1}}}$ $\lt 1 + n + \log(\log(n)) \; n^{\frac 1 2}$
$\frac {T(n)} n < 1 + \frac 1 n + \log(\log(n)) \; n^{-\frac 1 2}$
When $n \to \infty, \; 1 + \frac 1 n + \log(\log(n)) \; n^{-\frac 1 2} \to 1$.
So $\frac {T(n)} n$ is asymptotically upper-bounded by $1$.
But the trouble is, your formula $T(n) = T(1) + \sum_{k = 1}^{\log(\log(n)) -1} n^{\frac{1}{2^{k-1}}}$ is not correct, if I understand correctly the definition of $T(n)$.
Example, $T(81)=81+9+3+1$, while your formula would give $T(81)=1$, as $\log(\log(81)) = 1.4803...$
Hum, let's think about it.
The correct formula is rather:
$T(n) = T(1) + \sum_{k = 0}^{\log_2(\log_2(n))} n^{\frac{1}{2^k}}$
Which actually does not change the asymptotic analysis:
$\frac {T(n)} n > 1$, and
$\frac {T(n)} n \le 1 + \frac 1 n + \log_2(\log_2(n)) \; n^{-\frac 1 2}$, which $\to 1$ when $n \to \infty$.