Error solving the next recurrence: $T(n)=7T(n/2)+n^2$

Question

Hello I'm trying to solve this recurrence with the method that says the teacher that when you get to \begin{align*} T\bigg(\frac{n}{2^{k}} \bigg) \end{align*} you do \begin{align*} \frac{n}{2^{k}} &= 1 \qquad (\text{by definition})\\ k &= \log_{2}(n) \end{align*}

\begin{align*} T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &= 7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &= 7^{k}T\bigg(\frac{n}{2^{k}}\bigg) + \sum_{j=1}^{k-1} 7\frac{n}{2^{j}}+n^{2}\\ &= 7^{\log_{2}(n)} + \sum_{j=1}^{\log_{2}(n)-1} 7\bigg(\frac{n}{2^{j}}\bigg)^{2}+n^{2}\\ \end{align*}

After developing, I have left \begin{align*} 7^{\log_{2}(n)}+n^{2} \end{align*} But I know the solution is \begin{align*} n^{\log_{2}(7)} \end{align*}

What am I doing wrong?

Answer 1

Some of your sums have typos, but you already have the right answer.

Here's a useful fact about logarithms:

$a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$

Apply it to your answer, keeping in mind that $\lg 7 \approx 2.8 > 2$:

$O(7^{\lg n} + n^2) = O(n^{\lg 7} + n^2) = O(n^{\lg 7})$

Answer 2

There are indeed some typos as @Craig Gidney pointed out. Moreover you forgot the exponent for the '$7$' in the sum and the term $T(1)$...

I propose you the following solution (which is much similar to yours):

First of all let $n=2^k$ hence the initial recurrence turns into

$$T(2^k)=7\cdot T(2^{k-1})+4^k$$

Now setting $S(k)=T(2^k)$ we have

$$S(k)=7\cdot S(k-1)+4^k$$

Therefore we have

\begin{align*} S(k)&=7\cdot S(k-1)+4^k\\ 7\cdot S(k-1)&=7^2\cdot S(k-2)+7\cdot 4^{k-1}\\ 7^2\cdot S(k-2)&=7^3\cdot S(k-3)+7^2\cdot 4^{k-2}\\ &\vdots\\ 7^{k-1}\cdot S(1)&=7^k\cdot S(0)+\sum_{i=0}^{k-1}7^i4^{k-i} \end{align*}

Summing-up we are left with

$$S(k)=7^k\cdot S(0)-\frac{4}{3}\cdot (4^k-7^k)$$

and substituting back the value of $n$ we have

$$T(n)=n^{\log_2 7}\cdot T(1)-\frac{4}{3}(n^2-n^{\log_2 7})$$

for $n>0$.

Hope it helps.

Answer 3

Apparently the difference between $7^{log_2(n)}$ and $n^{log_2(7)}$ confused you (quite understandably). But take the base two logarithm on both sides:

$log_2(a^b) = log_2(a)·b$, so on the left side the logarithm is $log_2(7)·log_2(n)$, on the right side it is $log_2(n)·log_2(7)$. So both expressions are exactly the same.