1

I got for homework the following recurrence relation: $T(n)=n^\frac{2}{3}\cdot T(n^\frac{1}{3})+c $

and $T(1)=O(1) $ $\forall n\leq2 $

And this is what I got so far:

by using the iterative method I got that the for any $k$ :

$T(n)=n^{1-\frac{1}{3^k}}\cdot T(n^\frac{1}{3^{k+1}})+c+cn^\frac{2}{3}+cn^{\frac{2}{3}+\frac{2}{9}}+...+cn^{\frac{2}{3}+\frac{2}{9}+...+\frac{2}{3^{k-1}}} $

and the maximum level of the tree is for $k=log_3(log_2(n))$ then for $k=log_3(log_2(n))$ :

$T(n)=n^{1-\frac{1}{3^{log_3(log_2(n))}}}\cdot T(2)+c+cn^\frac{2}{3}+cn^{\frac{2}{3}+\frac{2}{9}}+...+cn^{\frac{2}{3}+\frac{2}{9}+...+\frac{2}{3^{log_3(log_2(n))-1}}} $

$T(n)=n^{1-\frac{1}{log_2(n)}}+c+cn^\frac{2}{3}+cn^{\frac{2}{3}+\frac{2}{9}}+...+cn^{\frac{2}{3}+\frac{2}{9}+...+\frac{2}{3^{log_3(log_2(n))-1}}} $

and $n^{1-\frac{1}{log_2(n)}}=\frac{n}{2}$

so,I get :

$T(n)=\frac{n}{2}+c+cn^\frac{2}{3}+cn^{\frac{2}{3}+\frac{2}{9}}+...+cn^{\frac{2}{3}+\frac{2}{9}+...+\frac{2}{3^{log_3(log_2(n))-1}}} $

also the sum in the power of the last element is : $\frac{2}{3}+\frac{2}{9}+...+\frac{2}{3^(log_3(log_2(n))-1)}=1-\frac{1}{log_2(n)} $

so, the last element is also equal to $\frac{n}{2}$ so far I got :

$T(n)=\frac{n}{2}+c+cn^\frac{2}{3}+cn^{\frac{2}{3}+\frac{2}{9}}+...+c\frac{n}{2} $

how to proceed from here?

USERUSER
  • 75

1 Answers1

1

With $n>0$ we have

$$ \frac{T(n)}{n} = \frac{T(n^{\frac 13})}{n^{\frac 13}}+\frac cn $$

Calling $R(n) = \frac{T(n)}{n}$ we follow with

$$ R(n) = R(n^{\frac 13})+\frac cn $$

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

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

now with $z = 3^u$ we follow with

$$ \mathcal{R}\left(3^u\right) = \mathcal{R}\left(3^{u-1}\right) + c 3^{-3^u} $$

Calling now $\mathbb{R}\left(\cdot\right) = \mathcal{R}\left(3^{(\cdot)}\right)$ we follow with

$$ \mathbb{R}\left(u\right) = \mathbb{R}\left(u-1\right) + c 3^{-3^u} $$

with solution

$$ \mathbb{R}\left(u\right) =c \left(c_0+\sum_{k=1}^{k=u}3^{-3^k}\right) $$

now, going backwards with $u = \log_3 z$ and $z = \log_3 n$ we get at

$$ T(n) = c \cdot n\left(c_0+\sum_{k=1}^{\log_3(\log_3 n)}3^{-3^k}\right) $$

Remember that $3^{-3^{\log_3(\log_3 n)}} = n^{-\frac 13}$ thus if $n = 3^{3^3}$ we have

$$ T(3^{3^3})= c\cdot 3^{3^3} \left(c_0+\sum_{k=1}^{3}3^{-3^k}\right) = c(7625597484987 c_0 + 282816956971) $$

Cesareo
  • 33,252