Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a constant, it's really difficult to apply tree method and master theorem here. Any hint? My thought is that let $c = \sqrt{n}$ such that $c^2 = n$ so we have $T(c^2) \leq cT(c) + c^2$ but I does not look good.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $k=k(n)$ be the smallest positive integer such that $n^{2^{-k}}<2$. Equivalently $k$ is the smallest positive integer such that $k>\log_2(\log_2(n))$. So, $$k=\lceil \log_2(\log_2(n))\rceil$$ Using repeatedly the inequality with $n,n^{2^{-1}},n^{2^{-2}},...,n^{2^{-k}}$ we get $$ \begin{align} T(n)&\leq n^{1/2}T(n^{1/2})+n\\ &\leq n^{1/2+1/4}T(n^{1/4})+2n\\ &\leq n^{1/2+1/4+1/8}T(n^{1/8})+3n\\ &...\\ &\leq n^{1/2+1/4+...+1/2^k}T(n^{2^{-k}})+kn\\ &=n^{1-2^{-k}}O(1)+kn\\ &\leq n^{1-1/\log_2(n)}O(1)+n\log_2(\log_2(n))\\ &=\frac{n}{2}O(1)+n\log_2(\log_2(n)) \end{align} $$
So, we get that $$T(n)\in O(n\log_2(\log_2(n)))$$
