What is the complexity for the recurrence relation: T(n) = 2T(n/2) + 5n^2

Question

T(n) = 2T(n/2) + 5n^2

T(1) = 7

T(n/2) = 2T(n/2) + 5(n/2)^2

Eventually I can write this out in general form:

T(n) = 2^k * T(n/2^k) + 5(n/2^(k-1))^2 * (2^(k-1) + ... 2^0)

I'm struggling with understanding how I would write out the second part as a summation

Because of the (n/2^(k-1))^2 I would expect for the resulting summation to look something like

$\sum_{i=0}^k \frac{1}{2^i}^2$

(The exponent is for the entire fraction, the denominator should be $(2^i)^2$, and the upper bound should be k-1

However the correct answer is simply $1/2i$

I can use a summation identity to eventually solve the question, I'm having trouble correctly writing out what the general form summation would look like.

As an aside, when can I use the master theory to solve these types of questions? Thank you!

T(n) = aT(n/b) + cn^k

Answer 1

Your summation is incorrect. If you draw this as a recursion tree, you will notice that there are $\lg n$ steps before you reach $T(1)$. Also, observe that there is a $2$ multiplied with $T\left(\dfrac n2\right)$ which means you have to multiply it with the entire expression for $T\left(\dfrac n2\right)$.

$$ \begin{align} T(n) &= 2T\left(\frac n2\right) + 5n^2 \\ &= 2\left(2T\left(\frac n4\right) + 5\left(\frac n2\right)^2\right) + 5n^2 = 4T\left(\frac n4\right) + 5\left(\frac{n^2}2\right) + 5n^2 \\ &= 4\left(2T\left(\frac n8\right) + 5\left(\frac n4\right)^2\right) + 5\left(\frac{n^2}2\right) + 5n^2 = 8T\left(\frac n8\right) + 5\left(\frac{n^2}4\right) + 5\left(\frac{n^2}2\right) + 5n^2 \\ &\qquad\qquad\vdots \\ &= nT(1) + 5\left(\frac{n^2}{2^{\lg (n - 1)}}\right) + 5\left(\frac{n^2}{2^{\lg(n - 2)}}\right)+\cdots + 5\left(\frac{n^2}4\right) + 5\left(\frac{n^2}2\right) + 5n^2 \\ &= 7n + 5{\color{red}{\sum_{i = 0}^{\lg (n) - 1}\frac{n^2}{2^i}}} = 7n + 5\cdot 2n(n - 1) = 10n^2 - 3n = \Theta\left(n^2\right) \end{align} $$

Answer 2

Substituting $n=2^k$, $k=0,1,2,\ldots$ we have $T(2^k) = 2 T(2^{k-1}) +5\cdot 4^k$. Computing the first few values of $T(2^k)$, we have \begin{align} T(2^0) &= 7\\ T(2^1) &= 2\cdot 7 + 5\cdot 4^1 = 34\\ T(2^2) &= 2\cdot 34 + 5\cdot 4^2 = 148\\ T(2^3) &= 2\cdot 148 + 5\cdot 4^3 = 616\\ T(2^4) &= 2\cdot 616 + 5\cdot 4^4 = 2512. \end{align} This suggests the pattern $T(2^k) = 2^k \left(10\cdot 2^k-3\right)$. Clearly $T(2^0) = 2^0(10\cdot 2^0-3) = 7 = T(1)$, and if $T(2^k) = 2^k \left(10\cdot 2^k-3\right)$ for some nonnegative integer $k$ then \begin{align} T(2^{k+1}) &= 2T(2^k) + 5\cdot 4^{k+1}\\ &= 2^{k+1} \left(10\cdot 2^k-3\right) + 5\cdot 4^{k+1}\\ &= 2^{k+1} \left(10\cdot 2^k-3\right) + 10\cdot 2^{2k+1}\\ &= 2^{k+1} \left(10\cdot 2^{k+1}-3\right), \end{align} so by induction this expression is correct for all $k\geqslant 0$.

Answer 3

As

$$ T\left(2^{\log_2 n}\right)=2T\left(2^{\log_2 \frac n2}\right)+5 n^2 $$

now considering the transformation

$$ \mathbb{T}(\cdot) = T\left(2^{(\cdot)}\right),\ \ \ z = \log_2 n $$

we have the recurrence

$$ \mathbb{T}(z)=2\mathbb{T}(z-1)+5\times 4^z $$

with solution

$$ \mathbb{T}(z) = 2^{z-1} \left(C_0+20 \left(2^z-1\right)\right) $$

and substituting backwards

$$ T(n) = \frac{C_1 n}{2}+10 (n-1) n $$

and considering the initial conditions we have

$$ T(n) = 10n^2-3n $$