What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$

Question

By unrolling the recursion, \begin{equation*} \begin{split} T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\ &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6 \\ &= (T(n^{\frac{1}{8}})+3) + 6 = T(n^{\frac{1}{8}}) +9 \\ \end{split} \end{equation*}

Claim: $T(n) = T(n^{\frac{1}{2^k}}) + 3 \cdot k$

Base Case: $k=1$ \begin{equation*} \begin{split} T(n) &= T(n^{\frac{1}{2^1}}) + 3 \cdot 1 \\ T(n) &= T(\sqrt{n}) + 3 \end{split} \end{equation*}

Inductive Hypothesis: Assume that k=i is true, \begin{equation*} \begin{split} T(n) &= T(n^{\frac{1}{2^i}}) + 3 \cdot i \\ &= (T(n^{\frac{1}{2^i+1}}+3) + 3 \cdot i \\ &= (T(n^{\frac{1}{2^i+1}}) + 3 \cdot (i +1) \\ \end{split} \end{equation*}

These are my questions...

1. I am unsure if my base case is correct
2. I am also not sure how to proceed (what value can I substitute in to get a closed form)

Any help would be appreciated!

Answer 1

Where are you using that T(n) = c for n <= 10? Your formula is wrong when the argument is less than 10. K = 1 is not the base case. N <= 10 is the base case.

Clearly T(n) = c for n <= 10, T(n) = c+3 if 10 < n <= 100, T(n) = c+6 if 100 < n <= 10,000, T(n) = c+9 if 10,000 < n <= 100,000,000 etc.

Let f(n) = log_10 (max (n, 10)) so for the four cases above we have f(n) = 1, 1 < f(n) <= 2, 2 < f(n) <= 4, 4 < f(n) <= 8 etc.

Let g(n) = ceil(log_2(f(n))), then g(n) = 0, 1, 2, 3 etc, and T(n) = c + 3 g(n).

Answer 2

Assume the following: $T(n) \leq c\log_2(\log_2(n)), n > 10$ and $T(4) = c$ as a base case (because $4^2 > 10$.)

Now we can proceed by induction:
Base case: $$c\log_2(\log_2(4)) = c\log_2(2) = c \geq T(4)$$ General case:
We know $T(\sqrt{n}) \leq c\log_2(\log_2(\sqrt{n}))$ (induction hypo.). Hence:

$$T(n) = T(\sqrt{n})+3 \leq c\log_2(\log_2(\sqrt{n})) + 3$$

We can rewrite the right term: $$c\log_2(\log_2(\sqrt{n})) + 3 = c\log_2\left(\frac 12 \log_2(n)\right) +3 = c\log_2(\log_2(n)) - c + 3$$ Let $c = 3$. This results in: $$T(n) = T(\sqrt{n})+3 \leq 3\log_2(\log_2(n)) - 3 + 3 = 3\log_2(\log_2(n))$$ Hence: $T(n) \leq 3\log_2(\log_2(n))$.

---

You can also show $T(n) \geq 3\log_2(\log_2(n))$ in the same manner. Thus $T(n)\in O(\log \log(n))$. I hope this helps.