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.

We can write $$\frac{T(n)}n=\frac{T(n^{4/5})}{n^{4/5}}+\frac54$$

Now we can change variable $S(n)=\frac{T(n)}{n}$. So, we get $$S(n)=S(n^{4/5})+\frac{5}{4}$$

Then I used the recurrence tree method by taking $n=2^{(\frac{5}{4})^k}$. I got $S(n)=O((log_{5/4}(log_2 n))^2)$. So, $$T(n)=O(n(log_{5/4}(log_2 n))^2)$$

I don't know, the answer doesn't look right. Can anyone please help me out? If anyone knows the final answer please let me know, so that I can check.

Thanks!

Answer 1

Derivation
Lets consider $n = 2^{(5/4)^k}$. Now we can evaluate step by step: $$ S(n) = S(2^{(5/4)^{k-1}}) + 5/4 = S(2^{(5/4)^{k-2}}) + 5/4 + 5/4$$ Notice that every time $k$ is reduced by one since: $$\left(2^{(5/4)^{k}}\right)^{4/5} = 2^{(5/4)^{k}\cdot(4/5)} = 2^{(5/4)^{k-1}}$$ Thus we can denote $S(n)$ as (assuming $S(2) = 0$ as base case): $$\sum_{i=1}^k 5/4 = (5/4)k $$ Now lets solve $n = 2^{(5/4)^k}$ for $n$. Apply $\log_2$ and then $\log_{5/4}$ on both sides: $k = \log_{5/4}(\log_2(n))$ and thus $S(n) = (5/4)\log_{5/4}(\log_2(n))$.

---

Test by plugging it in
You can simply plug your solution in to test it. For $S(n) = S(n^{4/5}) + 5/4$ you can obtain $S(n) = (5/4)\log_{5/4}(\log_2(n))$ by the recursion tree method (as described above). Lets plug this into our recurrence: $$S(n) = (5/4)\log_{5/4}(\log_2(n^{4/5}))+5/4 = (5/4)\log_{5/4}((4/5)\log_2(n))+5/4$$ And by the rules of logaritm: $$S(n) = (5/4)\log_{5/4}(\log_2(n))+(5/4)\log_{5/4}(4/5)+5/4$$ Notice $\log_{5/4}(4/5) = -1$ and things cancel out: $$S(n) = (5/4)\log_{5/4}(\log_2(n))-(5/4)+5/4 = (5/4)\log_{5/4}(\log_2(n))$$ Our expression for $S(n)$ fulfills the recurrence. Hence $$T(n)/n = S(n) \Rightarrow T(n) = (5/4)n\log_{5/4}\log_2(n)$$ A double logarithm looks scary but if often occurs when recurrences have the form $T(n) = aT(n^\alpha) +b$.