I've been given the recursive function:
$$ T(n) = n^{\frac{2}{3}}\ T(n^\frac{1}{3}) + C $$
$$ T(n <= 2) = O(1)$$
With $ n =2^{3^p} $ where p is a positive integer.
I need to find an upper bound for that sum.
The solution is that its $O(n)$ but I got only $O(log(log(n))$ (log – base 2)
My try:
$\Large 2^{3^p} = n \quad \implies \quad p = log_3(log(n))$
With a recursion tree I found out that the cost of level $i$ of the tree is $$\Large 2^{\Sigma_{j=1}^i 3^{p-j}}$$
So the total cost of the function is (p levels) :
$$Cost(n) = \Large \Sigma_{i=0}^p 2^{\Sigma_{j=1}^i 3^{p-j}}$$
I inferred that the biggest number of that sequence is when i=p.
So (replacing sum with multiplication) that sum is less than:
$$ <= \Large p \cdot 2^{\Sigma_{j=1}^p 3^{p-j}} $$
Calculating $\Large 2^{\Sigma_{j=1}^p 3^{p-j}}$ I got $\Large \frac{n}{2}$
So the total Cost is $$ <=\Large p \cdot \frac{n}{2} = O(n log(log(n)))$$
I know that the problem is replacing the sum with multiplication but I don't have any better idea to procceed, any help would be appreciated thank you for your time!
Edit:
I managed to get the expression:
$$ \Large Cost(n) <= \sum_{i=0}^p n^{1 – \frac{1}{3^i}} = n\sum_{i=0}^{log_3(log_2(n))} n^{- \frac{1}{3^i}} <=$$ $$ \int_0 ^{log(n)} n^{-x}\ dx = \frac{n}{ln(n)} – \frac{n^{1 – \frac{ln(n)}{ln(2)}}}{ln(n)} < \frac{n}{ln(n)} <= n \implies T(n) = O(n)$$
Best Answer
If you get rid of cubic roots you get $$T(n^3)=n^2T(n)+C$$
Notice that when you divide by $n^3$ you get something more homogeneous $\dfrac{T(n^3)}{n^3}=\dfrac{T(n)}n+\dfrac C{n^3}$
So let set $U(n)=\dfrac{T(n)}{n}$ and we have
$$U(n^3)=U(n)+\dfrac{C}{n^3}$$
Now let set $n=2^p$ and $T(n)=V(p)$ and we have
$$V(3p)=V(p)+\dfrac{C}{8^p}$$
Now let set $p=3^k$ and $V(p)=W(k)$ and we have
$$W(k+1)=W(k)+\dfrac{C}{8^{3^k}}$$
This last one is telescopic therefore $W(k)=W(0)+\sum\limits_{i=0}^{k-1} \dfrac{C}{8^{3^i}}$
The problem is that this sum, does not really have a closed form, but the exponential grows very quickly so the sum also converges very quickly and we can estimate that $W$ is basically constant, i.e. $W(k)=O(1)$, so that $T(n)=O(n)$.