Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$

Question

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!

Answer 1

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.