Solving the recurrence $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n$

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?

• It's your problem if you're not allowed to apply Akra–Bazzi. In real life such constraints are not imposed artificially. Feb 24, 2019 at 17:16
• @YuvalFilmus I understand. Thanks a lot! Feb 24, 2019 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.
• 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}$? Feb 24, 2019 at 17:30