I encountered this equation, and tried to solve it:
$T(n) = T(\sqrt{n})+log(n)$
Under the initial condition T(1)=1.
Can someone tell me why is this initial condition helpful?
I mean, of course $T(1)=T(\sqrt{1})+log(1)=T(1)$, but how do I use that to get to a solution? Does it tell me anything about $n>1$?
I've got this so far. For recursion depth k:
$T(n) = T(n^{\frac{1}{2^{k+1}}})+\sum_{i=0}^klog(n^{\frac{1}{2^k}})$
Now I'd like to use the initial condition, and say:
$T(n^{\frac{1}{2^{k+1}}})=T(1)=1 \rightarrow 1=n^{\frac{1}{2^{k+1}}}$
But this leads me into contradiction:
$0=log_n(1)=\frac{1}{2^{k+1}} \rightarrow 1=0$
So I'd have to say $T(n)=\Theta(1)$? The actual solution is $T(n)=\Theta(log(n))$ but I can't figure out how to get there.
Please help (:
You got to this point:
$$T(n) = T(n^{\frac{1}{2^{k+1}}})+\sum_{i=0}^{k}\log(n^{\frac{1}{2^i}})$$
Note, I swapped your $k$ for $i$ in the summand.
If we now take the limit as $k \to \infty$: \begin{eqnarray*} T(n) &=& T(n^{\frac{1}{2^{k+1}}})+\sum_{i=0}^{k}\frac{1}{2^i}\log(n) \\ &=& \lim_{k \to \infty} T(n^{\frac{1}{2^{k+1}}}) + \sum_{i=0}^{\infty}\frac{1}{2^i}\log(n) \\ &=& \lim_{k \to \infty} T(n^{\frac{1}{2^{k+1}}}) + 2\log(n) \\ &=& C + 2\log(n) \qquad\mbox{where $C$ is some constant} \end{eqnarray*}
Note that $\lim_{k \to \infty}T(n^{\frac{1}{2^{k+1}}}) $ exists because the other terms in the equation are finite.
We can use our boundary point to find $C$:
$$1 = T(1) = C + 2\log(1) = C$$
Therefore we have the solution:
$$T(n) = 1 + 2\log(n)$$