patternMinor
Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$
Viewed 0 times
sqrtreccurencestackoverflow
Problem
Note: this is from JeffE's Algorithms notes on Recurrences, page 5.
(1). So we define the recurrence $T(n) = \sqrt{n}T(\sqrt{n})+n$ without any base case. Now I understand that for most recurrences, since we're looking for asymptotic bounds, the base case wouldn't matter. But in this case, I don't even see where we could define the base case. Is there any number we are guaranteed to hit as we keep taking square roots starting from any integer Do we just define $T(n) = a$ for $nhttp://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
(1). So we define the recurrence $T(n) = \sqrt{n}T(\sqrt{n})+n$ without any base case. Now I understand that for most recurrences, since we're looking for asymptotic bounds, the base case wouldn't matter. But in this case, I don't even see where we could define the base case. Is there any number we are guaranteed to hit as we keep taking square roots starting from any integer Do we just define $T(n) = a$ for $nhttp://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
Solution
You should really be asking a third question: what happens if $n$ isn't a perfect square. The answer to this question is that the actual recurrence should have $T(\lfloor \sqrt{n} \rfloor)$ or $T(\lceil \sqrt{n} \rceil)$ instead of $T(\sqrt{n})$, though in the analysis we will only consider inputs which are "recursive" squares.
Regarding your first question, there can be more than one base case. For example, perhaps $T(n) = 1$ for all $n \leq 100$. You are guaranteed to eventually hit this base case. In this case, as in most cases, the exact form of the base case doesn't affect the big Theta asymptotics (but it does affect the hidden constant).
Finally, regarding your second question, suppose that your base case specifies $T(n)$ for $n \leq C$. The recursion tree (which is a particular interpretation of some features of the recurrence) has the following form:
The recursion terminates when the instance has size at most $C$, and this happens when $n^{1/2^d} \leq C$. At the point that this happens, we have $n^{1/2^{d-1}} > C$ (assuming $n > C$), and so $\sqrt{C} < n^{1/2^d} \leq C$. Taking the logarithm, $\frac{1}{2} \log C < \frac{\log n}{2^d} < \log C$ and so $\frac{\log n}{2^d} = \Theta(1)$, implying $2^d = \Theta(\log n)$. We can conclude that $d \approx \log\log n$. This is the number of layers in the tree. Jeff uses $C = 2$, which is how he gets his particular formula.
Regarding your first question, there can be more than one base case. For example, perhaps $T(n) = 1$ for all $n \leq 100$. You are guaranteed to eventually hit this base case. In this case, as in most cases, the exact form of the base case doesn't affect the big Theta asymptotics (but it does affect the hidden constant).
Finally, regarding your second question, suppose that your base case specifies $T(n)$ for $n \leq C$. The recursion tree (which is a particular interpretation of some features of the recurrence) has the following form:
- The root is one instance of size $n$.
- The root has $\sqrt{n}$ children which are instances of size $\sqrt{n}$.
- Each node at depth 1 has $\sqrt{\sqrt{n}} = n^{1/4}$ children which are instances of size $\sqrt{\sqrt{n}} = n^{1/8}$.
- More generally, a node at depth $d$ is an instance of size $n^{1/2^d}$. You can prove this by induction by checking the case $d = 0$ (where $n^{1/2^d} = n$) and calculating $\sqrt{n^{1/2^d}} = n^{1/2^{d+1}}$.
The recursion terminates when the instance has size at most $C$, and this happens when $n^{1/2^d} \leq C$. At the point that this happens, we have $n^{1/2^{d-1}} > C$ (assuming $n > C$), and so $\sqrt{C} < n^{1/2^d} \leq C$. Taking the logarithm, $\frac{1}{2} \log C < \frac{\log n}{2^d} < \log C$ and so $\frac{\log n}{2^d} = \Theta(1)$, implying $2^d = \Theta(\log n)$. We can conclude that $d \approx \log\log n$. This is the number of layers in the tree. Jeff uses $C = 2$, which is how he gets his particular formula.
Context
StackExchange Computer Science Q#77090, answer score: 7
Revisions (0)
No revisions yet.