4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ In the different passages you forgot to adjust the value of $n^2$ and also to multiply the term for the correct power of $7$. Have a look at my solution. $\endgroup$ – Maczinga Feb 26 '17 at 10:21
  • 1
    $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Feb 26 '17 at 12:52
6
$\begingroup$

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})$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.