# What is the asymptotic bound for $T(n)= 3T(\sqrt[3]{n})+n^3$?

What is the asymptotic bound? How do you get to the result?

$$T(n)= 3 \cdot T(\sqrt[3]{n})+n^3$$

• Calculate the difference between T(n) and n^3 for n = 2^27. See if that gives you some idea. Commented Jul 10, 2021 at 13:16

The lower bound of $$T(n)\mathcal={\Omega}(n^3).$$ Because of $$T(n)$$ have a term $$n^3.$$

To find the upper bound we can use induction: $$T(n)\leq cn^3$$ $$=3cn+n^3\leq cn^3$$ As $$n\to \infty$$ , and for all $$c\geq 3$$ $$=3cn+n^3\leq cn^3.\hspace{10pt}\square$$ So $$T(n)=\theta(n^3).$$

Use a change of variable: $$n = a^k$$, $$T(a^k) = t(k)$$ gives:

$$t(k) = 3 t(k/3) + a^{3 k}$$

Apply the Master Theorem to this.

• $T(n)=3.T(n^\frac{1}{3})+n^3$ Suppose $n=a^k$ then,$T(a^k)=3.T(a^\frac{k}{3})+a^{3k}$ Assuming, $T(a^k)=S(k)$ we shall have $S(k)=3.S(\frac{k}{3})+a^{3k}$. Why did your $a^{3k}$ become $3k$ Commented Jun 10, 2021 at 6:51
• @AbhishekGhosh. Thank you. What math tool do you use to get to this types of equations please? Is it linear recurrence equation? Also, is $S(k/3) = T(a^{k/3})$? What is the advantage of using concise equation every time from $T(n)$ to $S(k)$ please?
– Avv
Commented Sep 23, 2021 at 19:33
• Yes $S(\frac{k}{3})=T(a^{\frac{k}{3}})$. We use these sort of transformation with a hope that we can convert the recurrence relation into a known form easily solvable by Master Method (a cookbook method). But unfortunately, I guess it cannot be solved using master method. Commented Sep 24, 2021 at 8:54

As

$$T\left(3^{\log_3n}\right)=3T\left(3^{\log_3 \sqrt[3]{n}}\right)+n^3$$

making $$\mathcal{T}\left(\cdot\right)= T\left(3^{(\cdot)}\right)$$ and $$z= \log_3 n$$ we follow with

$$\mathcal{T}\left(z\right)= 3\mathcal{T}\left(\frac z3\right)+3^{3z}$$

now with an analog procedure, making $$\mathbb{T}\left(\cdot\right)=\mathcal{T}\left(3^{(\cdot)}\right)$$ and $$\mu = \log_3 z$$ we follow with the recurrence

$$\mathbb{T}\left(\mu\right)=3\mathbb{T}\left(\mu-1\right)+3^{3\cdot 3^{\mu}}$$

now this recurrence has as solution

$$\mathbb{T}\left(\mu\right)=\frac 13\log_3 \mu\left(c_0+\sum_{k=0}^{u-1}3^{3^{k+2}-k}\right)$$

and now going backwards with $$\mu=\log_3 z$$ and $$z = \log_3 n$$ we arrive at

$$T(n) = \frac 13\log_3 n\left(c_0+\sum_{k=0}^{\log_3(\log_3 n)-1}3^{3^{k+2}-k}\right)$$

now considering $$k = \log_3(\log_3 n)-1$$ we have for sure

$$T(n) \ge n^3$$