What is the upper and lower bound for $T(n) = T(sqrt{n}) +3$, assuming that $T(n)$ is a constant for $nleq 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...

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

Any help would be appreciated!

plshelp · Answer

Assume the following: $T(n) leq clog_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:
$$clog_2(log_2(4)) = clog_2(2) = c geq T(4)$$
General case:
We know $T(sqrt{n})  leq clog_2(log_2(sqrt{n}))$ (induction hypo.). Hence:
$$T(n) = T(sqrt{n})+3 leq clog_2(log_2(sqrt{n})) + 3$$
We can rewrite the right term:
$$clog_2(log_2(sqrt{n})) + 3 = clog_2left(frac 12 log_2(n)right) +3 = clog_2(log_2(n)) - c + 3$$
Let $c = 3$. This results in:
$$T(n) = T(sqrt{n})+3 leq 3log_2(log_2(n)) - 3 + 3 = 3log_2(log_2(n))$$
Hence:
$T(n) leq 3log_2(log_2(n))$.

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

gnasher729 · Answer

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

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

2 Answers

Add your own answers!

Ask a Question