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$

1 Answer 1

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$
6
  • $\begingroup$ But I am getting square of double logarithm. $\endgroup$
    – uuuuuuuuuu
    Oct 11, 2020 at 9:28
  • 1
    $\begingroup$ oopsie I didn't notice. I'll add how I applied the recursion tree method. $\endgroup$
    – plshelp
    Oct 11, 2020 at 9:30
  • $\begingroup$ @uuuuuuuuuu can you know spot where you went wrong while applying the recursion tree method? $\endgroup$
    – plshelp
    Oct 11, 2020 at 9:44
  • $\begingroup$ Ok, I will post my solution. Give me some time, ok. $\endgroup$
    – uuuuuuuuuu
    Oct 11, 2020 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, 2020 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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