I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$.
These are all the data I got. where do i start from? what is the base case? i'm not really sure... Thanks!
I assume $\sqrt{n}$ refers to the integer square root, where you round down.
You prove it by strong induction. Assume that $T(n)\le Cn\log \log n$ for some all $n$ satisfying $n_0\le n<m$, for a constant $C$ to be determined later. Then $$ T(m)=\sqrt{m}T(\sqrt{m})+m\le \sqrt{m}\cdot C\sqrt{m}\log \log \sqrt{m}+m =m\cdot \big(C\log \log m+C\log \tfrac12 +1\big) $$ We want this last expression to at most $C\log\log m$, completing the strong induction proof. Assuming this implies $C\ge\frac1{\log 2}$.
To figure out the base cases, look at what the induction hypothesis needs. For the above to work, you need the $\sqrt{m}$ to be previously proven, so the set of base cases need to be a set $B$ such that repeated application of $\sqrt{\cdot}$ always sends an integer to $B$. It turns out that $B=\{2,3\}$ works. Therefore, this induction proof works for any choice of $C$ such that $C\ge \frac1{\log 2}$ and $T(2)\le C\cdot 2\log \log 2$ and $T(3)\le C\cdot 3\log \log 3$.