Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Yesterday in class, we were analyzing the Karatsuba multiplication algorithm and how it applies to recurrence equations. Time ran short, and I feel I missed how to solve the final summation.

First, we defined the recurrence equation as

$$T(n) = 3T \left(\frac{n}{2}\right) + 4n$$

and applied a recurrence tree such like

$$T(n) = 3T \left(\frac{n}{2}\right) + 4n \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^0$$

$$T\left(\frac{n}{2}\right) = 3T \left (\frac{n}{4} \right) + 4\left(\frac{n}{2}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^1$$

$$T\left(\frac{n}{4}\right) = 3T \left (\frac{n}{8} \right) + 4\left(\frac{n}{4}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^2$$

$$T\left(\frac{n}{8}\right) = 3T \left (\frac{n}{16} \right) + 4\left(\frac{n}{8}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^3$$

Because the denominiator increases in a logarithmic fashion, we defined the summation as

$$\sum_{x=0}^{log_2n} 4n \cdot \left(\frac{3}{2}\right)^x$$

Time was running short, so several steps were skipped, and the final solution was given as

$$9\cdot 3^{log_2n} = 9n^{log_23} = 9n^{1.58} = O(n^{1.58})$$

based on the properties

$$a^{lg\, b} = b^{lg\, a}\: \text{and}\: log_2 3 \approx 1.58$$

I've tried applying the summation formula

$$\sum_{x=0}^{n}r^x = \frac{r^{n+1}-1}{r-1}$$

with this result, and end up with

$$\sum_{x=0}^{n}r^x = \frac{r^{n+1}-1}{r-1} = \sum_{x=0}^{log_2 n} 4n \cdot \left(\frac{3}{2}\right)^x $$

$$= 4\left(n\cdot \frac{\frac{3}{2}^{lg_2n+1}-1}{\frac{3}{2}-1}\right) = 4\left(n \cdot \frac{\frac{3}{2}^{log_2n+1}-1}{\frac{1}{2}}\right) = 2\left(n \cdot \frac{3}{2}^{log_2n+1}+1\right) $$

$$=2n \cdot 3^{log_2n+1} + 2$$

which is very different than the solution given. Where did I go wrong?

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

The crucial mistake is that you passed somehow from $$ (\frac32)^{(\log_2 n) +1} $$ to $$ 3^{(\log_2 n )+ 1}. $$ Using the rough formula that $$ \sum_{x=0}^n r^x = O(r^n) \qquad \qquad\text{if $r>1$}, $$ you should get $$ O(n (\frac32)^{\log_2 n})=O(n e^{(\ln n) \frac{\ln \frac32}{\ln 2}}) = O(n^{1+\frac{\ln \frac32}{\ln 2}}). $$ Since $$ 1 + \frac{\ln \frac32}{\ln 2} = \frac{\ln 3}{\ln 2} = \log_2 3 = 1.58496... $$ this is the same as the result you got in class.

share|improve this answer
add comment

This recurrence has the nice property that we can compute explicit values for $T(n)$ the same way as was done here, for example.

Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary digit representation of $n.$ It is not difficult to see that with $T(0)=0$ we have $$ T(n) = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 3^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Now for an upper bound consider $n$ consisting only of one digits, giving $$ T(n) \le 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j \left( 2^{\lfloor \log_2 n \rfloor + 1} - 2^j\right) $$ which is $$ 4 \left( 2^{\lfloor \log_2 n \rfloor + 1} \frac{(3/2)^{\lfloor \log_2 n \rfloor + 1}-1}{3/2-1} - \sum_{j=0}^{\lfloor \log_2 n \rfloor}3^j \right) = 4 \left(2 \left( 3^{\lfloor \log_2 n \rfloor + 1} - 2^{\lfloor \log_2 n \rfloor + 1}\right) - \frac{3^{\lfloor \log_2 n \rfloor + 1}-1}{3-1} \right) = 2\times 3^{\lfloor \log_2 n \rfloor + 2} - 2^{\lfloor \log_2 n \rfloor + 4} + 2.$$ For a lower bound, take all digits zero except the leading one, getting $$ T(n) \ge 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j 2^{\lfloor \log_2 n \rfloor} = 2^{\lfloor \log_2 n \rfloor + 2} \frac{(3/2)^{\lfloor \log_2 n \rfloor + 1}-1}{3/2-1} = 4\times 3^{\lfloor \log_2 n \rfloor + 1} - 2^{\lfloor \log_2 n \rfloor + 3} .$$ The lower bound and the upper bound taken together show that $$ T(n) \in \Theta\left(3^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\log_2 3 \lfloor \log_2 n \rfloor} \right) = \Theta\left(n^{\log_2 3}\right).$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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