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$
$\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$– Yuval FilmusFeb 24, 2019 at 17:16
-
$\begingroup$ @YuvalFilmus I understand. Thanks a lot! $\endgroup$– xsj0101Feb 24, 2019 at 17:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Feb 24, 2019 at 17:15
-
$\begingroup$ C(n) should be the depth of the tree, which is log(log n). $\endgroup$– xsj0101Feb 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$– xsj0101Feb 24, 2019 at 17:30
-
-
$\begingroup$ Ah thanks I got it now. There was a skipped step $\endgroup$– xsj0101Feb 24, 2019 at 17:34