Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$.

Question

I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term. I am trying to remove this term, so I tried doing substitution like $n^{1/5}=m$ but clearly this is not helping. Can anyone give any suggestions?

Thanks!

Answer 1

HINT: Dividing by $n$, you get:$$\frac{T(n)}n=\frac{T(n^{4/5})}{n^{4/5}}+\frac54.$$

Answer 2

With $a = \frac 45 $ we have

$$ T\left(e^{\ln n}\right)=n^{\frac a4}T\left(e^{\ln n^a}\right)+\frac na $$

now calling

$$ \cases{ \mathcal{T}(\cdot) = T\left(e^{(\cdot)}\right)\\ z = \ln n } $$

we follow with

$$ \mathcal{T}(z) = e^{\frac a4 z}\mathcal{T}(a z)+\frac{e^z}{a} $$

and now making

$$ \cases{ \mathbb{T}(\cdot) = \mathcal{T}\left(a^{(\cdot)}\right)\\ u = \log_a z } $$

we follow with

$$ \mathbb{T}(u)= e^{\frac a4 a^u}\mathbb{T}\left(u+1\right)+\frac{e^{a^u}}{a} $$

or

$$ \frac{\mathbb{T}(u)}{e^{a^u}} = \frac{\mathbb{T}(u+1)}{e^{a^{u+1}}}+\frac 1a $$

now calling $\Theta(u) = \frac{\mathbb{T}(u)}{e^{a^u}}$ we follow with

$$ \Theta(u) = \Theta(u+1) + \frac 1a $$

with solution

$$ \Theta(u) = c_1-\frac{u}{a} \Rightarrow \mathbb{T}(u) = e^{a^u}\left(c_1-\frac{u}{a}\right) $$

and with backwards substitutions we arrive at

$$ T(n) = n\left(c_1-\frac{\log_a\left(\ln n\right)}{a}\right) $$