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$
2
  • $\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, 2019 at 17:16
  • $\begingroup$ @YuvalFilmus I understand. Thanks a lot! $\endgroup$
    – xsj0101
    Feb 24, 2019 at 17:25

1 Answer 1

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

Your Answer

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

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