1
$\begingroup$

The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on $$ T(n) = 9T(\sqrt[3]n) + \Theta(1). $$ I am able to get the tree started and find a pattern with the sub-problems, but I am having difficulty finding the total cost of the running times throughout the tree. I cannot figure out how to get the number of sub-problems at depth $i$ when $n=1$. I have a feeling the answer is $O(\log_3 n)$, but I cannot verify that at the moment. Any help would be appreciated.

The recurrence can be written as $$T(n) = 9T(\sqrt[3]n) + C, $$ where $C$ is some constant, since any constant will always be treated as 1 asymptotically. My recursion tree is explained by each level below:

Level 0: This is the constant $C$

Level 1: $T(\sqrt[3]n)$ is written 9 times which represent the sub-problems of $C$. This adds up to $9C\sqrt[3]n$.

Level 2: Each of the 9 sub-problems from level 1 gets divided into 9 more sub-problems, which are each written as $T(\sqrt[9]n)$. All of these add up to $81C\sqrt[9]n$.

Sub-Problem Sizes and Nodes: The number of nodes at depth $i$ is $9^i$. We know that the sub-problem size for a node at depth $i$ is $n^{1/3^i}$. The problem size hits $n=1$ when this size equals 1. Solving for $i$ yields:

$$ (n^{1/3^i})^{3i} = 1^{3i} n = 1^{3i}. $$

This results in $n$ being 1 which doesn't give a logarithmic form!

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Evil Jun 21 at 1:27
2
$\begingroup$

You can solve this using the master theorem, whose proof uses a recursion tree argument.

Define $S(n) = T(2^n)$. The main observation is that $\sqrt[3]{2^n} = 2^{n/3}$, and so $$ S(n) = 9S(n/3) + O(1). $$ The solution is $S(n) = \Theta(n^2)$, and so $$ T(n) = S(\log n) = \Theta(\log^2 n).$$

You can also open the recurrence directly, obtaining $$ T(n) \propto 1 + 9n^{1/3} + 9^2 n^{1/3^2} + 9^3 n^{1/3^3} + \cdots. $$ The general term is $9^i n^{1/3^i}$. The recurrence will terminate when $n^{1/3^i} \approx 1$, which happens when $3^i \approx \log n$, that is, when $i \approx \log_3 \log n$. For this value of $i$, $$ 9^i = 3^{2\log_3 \log n} = \log^2 n. $$ This is the value of the bottom level of the tree. The contribution of the other levels is negligible in comparison, which is something you have to prove by calculation.

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