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

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!

• 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. – Evil Jun 21 '19 at 1:27

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.