0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ But I am getting square of double logarithm. $\endgroup$ – uuuuuuuuuu Oct 11 '20 at 9:28
  • 1
    $\begingroup$ oopsie I didn't notice. I'll add how I applied the recursion tree method. $\endgroup$ – plshelp Oct 11 '20 at 9:30
  • $\begingroup$ @uuuuuuuuuu can you know spot where you went wrong while applying the recursion tree method? $\endgroup$ – plshelp Oct 11 '20 at 9:44
  • $\begingroup$ Ok, I will post my solution. Give me some time, ok. $\endgroup$ – uuuuuuuuuu Oct 11 '20 at 9:48
  • $\begingroup$ You don't have to - if you can find the difference between mine and yours it's fine. (for my previous comment *know = now) $\endgroup$ – plshelp Oct 11 '20 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.