I need to solve the following recurrence relation: $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)=T(e^x)$. I was able to get to $F(x)= e^{3x/4} \cdot F(x/4)+ e^x$. However, the master theorem still doesn't apply at this stage. How can I proceed?

  • $\begingroup$ It's your problem if you're not allowed to apply Akra–Bazzi. In real life such constraints are not imposed artificially. $\endgroup$ Feb 24 '19 at 17:16
  • $\begingroup$ @YuvalFilmus I understand. Thanks a lot! $\endgroup$
    – xsj0101
    Feb 24 '19 at 17:25

You can just expand it: $$ \begin{align*} T(n) &= n + n^{3/4} T(n^{1/4}) \\ &= n + n^{3/4}\cdot [n^{1/4}+ n^{3/16}\cdot T(n^{1/16})] \\ &= n + n + n^{3/4} \cdot n^{3/16} T(n^{1/16}) \\ &= n + n + n + n^{3/4} \cdot n^{3/16} \cdot n^{3/64} T(n^{1/64}) \\ &= \cdots \end{align*} $$ We see that $T(n) = C(n) n$, where $C(n)$ is the number of times we need to apply $n \mapsto n^{1/4}$ until the answer drops below some constant.

I'll let you figure out $C(n)$, and so complete this exercise.

  • $\begingroup$ C(n) should be the depth of the tree, which is log(log n). $\endgroup$
    – xsj0101
    Feb 24 '19 at 17:24
  • $\begingroup$ Right – that completes the solution. $\endgroup$ Feb 24 '19 at 17:24
  • $\begingroup$ I'm still confused about some part. Isn't $T(n^{1/4})=(n^{1/4})^{3/4}*T((n^{1/4})^{1/4})+n^{1/4}$? $\endgroup$
    – xsj0101
    Feb 24 '19 at 17:30
  • $\begingroup$ That's indeed right. $\endgroup$ Feb 24 '19 at 17:31
  • $\begingroup$ Ah thanks I got it now. There was a skipped step $\endgroup$
    – xsj0101
    Feb 24 '19 at 17:34

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.