Let $T(n) = \sqrt{n} T(\sqrt{n}) + c\,n$ for $n \gt 2$ and some positive constant $c$ and $T(2) = 1$.
I know the Master theorem, but I'm not sure as to how we could solve this relation using it. Any insight would be helpful.
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
|||||||||||||
|
migrated from stackoverflow.com Oct 31 '12 at 22:42
|
We will use Raphael's suggestion and unfold the recurrence. In the following, all logarithms are base 2. We get $$ \begin{align*} T(n) &= n^{1/2} T(n^{1/2}) + cn \\ &= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\ &= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\ &= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\ & \ldots \\ &= \frac{n}{2} T(2) + c n \beta(n) \end{align*}. $$ where $\beta(n)$ is how many times you have to take the square root to start with n, and reach 2. It turns out that $\beta(n) = \log \log n$. How can you see that? Consider: $$ \begin{align*} n &= 2^{\log n}\\ n^{1/2} &= 2^{\frac{1}{2} \log n} \\ n^{1/4} &= 2^{\frac{1}{4} \log n} \\ \ldots \end{align*} $$ So the number of times you need to take the square root in order to reach 2 is the solution to $\frac{1}{2^t} \log n \approx 1$, which is $\log \log n$. So the solution to the recursion is $c n \log \log n + \frac{1}{2}n$. To make this absolutely rigorous, we should use the substitution method and be very careful about how things get rounded off. When I have time, I will try to add this calculation to my answer. |
|||||||||
|
|
If you write $m=\log n \space$ you have $T(m) = {m \over 2}\cdot T({m\over 2}) + c\cdot 2^m\space$. Now you know the recursion tree has hight of order $O(\log m)$, and again it's not hard to see it's $O(2^m)\space$ in each level, so total running time is in: $O((\log m) \cdot 2^m)\space$, which concludes $O(n \cdot \log \log n)\space$ for $n$. In all when you see $\sqrt n $ or $n^{a \over b}, a<b \space$, is good to check logarithm. P.S: Sure proof should include more details by I skipped them. |
|||
|
|
|
Let's follow Raphael's suggestion, for $n = 2^{2^k}$: $$ \begin{align*} T(n) = T(2^{2^k}) &= 2^{2^{k-1}} T(2^{2^{k-1}}) + c2^{2^k} \\ &= 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) + c(2^{2^k} + 2^{2^k}) \\ &= \cdots \\ &= 2^{2^{k-1}+2^{k-2}+\cdots+2^0} T(2^{2^0}) + c(2^{2^k} + 2^{2^k} + \cdots + 2^{2^k}) \\ &= 2^{2^k-1} + ck2^{2^k} \\ &= (c\log\log n + 1/2)n. \end{align*} $$ Edit: Thanks Peter Shor for the correction! |
|||||||||
|
