1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ C(n) should be the depth of the tree, which is log(log n). $\endgroup$ – xsj0101 Feb 24 at 17:24
  • $\begingroup$ Right – that completes the solution. $\endgroup$ – Yuval Filmus Feb 24 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 at 17:30
  • $\begingroup$ That's indeed right. $\endgroup$ – Yuval Filmus Feb 24 at 17:31
  • $\begingroup$ Ah thanks I got it now. There was a skipped step $\endgroup$ – xsj0101 Feb 24 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.