8
$\begingroup$

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 $n<b$, for some reals $a$, $b$?

(2). On page 7, Erickson gets that the number of layers in the recursion tree L will satisfy $n^{{2}^{-L}} = 2$. Where is this coming from? I have no idea. I see that the number of leaves in the tree should sum to $\sqrt(n)\sqrt(n) = n$, but I have no idea where to go from there.

Any help is appreciated!

Notes I'm looking at: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

$\endgroup$
7
$\begingroup$

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 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.

$\endgroup$
4
$\begingroup$

Answering your first question. Alternative to using the upper bound and lower bound to achieve a base case, one option is that you could assume the form of $n$.

Take, for example, the mergesort recursion:

$$T(n) = 2c \cdot T\left( \frac{n}{2} \right) + c \cdot n $$

Clearly, most $n$ will not divide evenly into integers. It is then pretty common to assume that $n$ is of the form: $$ n = 2^k \quad\quad k \in \mathbb{N}$$

This implies every $n$ is a positive power of $2$, thus resolving our base case always to $1$. Alternatively we could make the base case $c$ instead of $1$ by assuming $n$ is of the form: $$ n = c \cdot 2^k \quad\quad k \in \mathbb{N}, c \in \mathbb{N}^+$$

We can apply this to our recurrence:

$$T(n) = \sqrt{n} \cdot T\left(\sqrt{n}\right) + n$$

Assume $n$ is of the form: $$n = c^{2^k} \quad \quad k \in \mathbb{N}, c \in \mathbb{N}^+$$ Then the base case will always resolve to a constant $c$.

Now if you can prove it under this assumption, you could then go on to make a proof for $n$ values that do not have this form. One approach would be by attempting to bound it by the next highest (or lowest) $n$ that does have that form.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.