0
$\begingroup$

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!

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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