Solving Recurrence Relation Using Substitution/Geometric Series

Question

$$ T(n) =4T(\frac{n}{2})+ n^\frac{5}{2} $$

I'm having trouble solving this recurrence relation above to identify the time complexity below by using substitution/plugging. I'm able to do it using master's theorem and I get $$ T(n) = \theta(n^\frac{5}{2})$$ but I'd like to be able to understand how to do it using substitution (is one easier /more intuitive to use? I tried using substitution where I continuously plugged in n/2 for n but I wasn't able to get a generalized case form.

Answer 1

First, we can expand T(n) infinitely.

$T(n)=n^{\frac{5}{2}}+4(\frac{n}{2})^{\frac{5}{2}}+16(\frac{n}{4})^{\frac{5}{2}}+...$ Change this into a summation.

$T(n)=\sum_{i=0}^{\infty}4^i(\frac{n}{2^i})^{\frac{5}{2}}$ Distribute exponent.

$T(n)=\sum_{i=0}^{\infty}2^{2i}\frac{n^{\frac{5}{2}}}{2^{\frac{5i}{2}}}$ Simplify.

$T(n)=\sum_{i=0}^{\infty}(\frac{1}{\sqrt{2}})^i n^{\frac{5}{2}}$ Expand.

Expanding the summation gives us:

$n^{\frac{5}{2}}(1+\frac{1}{\sqrt{2}}+\frac{1}{2}+\frac{1}{2\sqrt{2}}+...)$

Which can be simplified to $(2+\sqrt{2})n^{\frac{5}{2}}$

I'm assuming $\theta$ is $2+\sqrt{2}$?

Answer 2

Have a look at some other examples I treated:

solving recurrence equations and get complexity T(n)...

Recurrent Relation Problem

First rewrite to the form $$T(bn)=a\,T(n)+f(n)$$

We have $T(2n)=4T(n)+(2n)^{5/2}$.

Refering to my second post , let's try a $V$ substitution first!

This substitution is more powerful because a lot of stuff cancels on the way. But sometimes it does not work, in this case fall back to a simpler $U$ substitution, but less things cancels.

We choose to divide by $n^{3/2}$ so as to get $\dfrac{f(n)}{n^{3/2}}$ linear.

So let's have $V(n)=4\dfrac{T(n)}{n^{3/2}}+cn$

Reporting in our equation we get:

$V(2n)=4\dfrac{T(2n)}{(2n)^{3/2}}+2cn=4\dfrac{4T(n)+(2n)^{5/2}}{(2n)^{3/2}}+2cn=\underbrace{\dfrac{4}{2^{3/2}}}_{=\sqrt{2}}\dfrac{4T(n)}{n^{3/2}}+(8+2c)n$

Now we factorize by $\sqrt{2}$ to make $V(n)$ appear again.

$V(2n)=\sqrt{2}\left(\dfrac{4T(n)}{n^{3/2}}+\underbrace{\dfrac{8+2c}{\sqrt{2}}}_{\text{to identify to }c}n\right)=\sqrt{2}\ V(n)\quad$ for $\sqrt{2}c=8+2c\iff c=\frac{8}{\sqrt{2}-2}$

We now have an induction relation for $V(n)$ which is much simpler $$V(2n)=\sqrt{2}V(n)$$

$V(2^p)=\sqrt{2}V(2^{p-1})=\cdots=(\sqrt{2})^pV(1)$

So for $n=2^p\iff \ln(n)=p\ln(2)\quad$ we get $V(n)=\exp(p\ln(\sqrt{2})V(1)=\exp(\frac 12\ln(n))V(1)=V(1)\sqrt{n}$

Or simply $$V(n)=k\sqrt{n}$$

We can now report into the formula for $T(n)$ to get:

$$T(n)=\left(V(n)-cn\right)\dfrac{n^{3/2}}{4}= \alpha\ n^2 + \beta\ n^{5/2}$$

And this expression is compatible with what you get from master theorem approximation $T(n)=O(n^{5/2})$. The only difference here, is that we get a little more precise result.

Edit: a remark on Alien's result. The true value of $\beta=-\dfrac c4=\dfrac 2{2-\sqrt{2}}=2+\sqrt{2}\ $ is the same as his.