2
$\begingroup$

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm -

$$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with the base case $T(1) = 1$ and $n = 2^j$, I have been able to reduce the formula to the following form:

$$T(2^j) = 7^j + \frac{3}{2}\,4^{j} \left[\left(\frac74\right)^j - 1\right],$$ the last step in this formula is plugging in $n = 2^j$ to get an expression in $n$ but somehow I can't reduce it further, can someone tell how to do this to get an expression in $n$?

$\endgroup$
  • $\begingroup$ Try using $j=\log_2 n$ and $a^{log_2 n}=2^{\log_2 a \log_2 n}=n^{\log_2 a}$. $\endgroup$ – lhf Sep 26 '13 at 15:50
  • $\begingroup$ done got it thanks a lot :) $\endgroup$ – AnkitSablok Sep 26 '13 at 15:51
  • $\begingroup$ Add your own answer then. $\endgroup$ – lhf Sep 26 '13 at 15:52
  • $\begingroup$ $(5/2)*n^(lg7) - (3/2)*n^2$ $\endgroup$ – AnkitSablok Sep 26 '13 at 15:57
  • $\begingroup$ I meant as a true answer, not as a comment. $\endgroup$ – lhf Sep 26 '13 at 16:01
1
$\begingroup$

We can compute exact formulas for your recurrence and not just at powers of two. Suppose we first solve the recurrence $$S(n) = 7 S(\lfloor n/2\rfloor) + \frac{18}{16} n^2$$ with $S(0)=0.$ (This will produce $S(1) = \frac{18}{16}$ instead of one, which we'll correct later.)

Then let $$n= \sum_{k=0}^{\lfloor \log_2 n\rfloor} d_k 2^k$$ be the binary representation of $n$ and unroll the recursion to get the following exact formula for $S(n):$ $$S(n) = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^{k-j} \right)^2 = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^k \right)^2.$$ To get an upper bound on this consider a string of one digits, which gives $$S(n)\le \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} 2^k \right)^2 = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j \left(2^{\lfloor \log_2 n\rfloor+1}- 2^j\right)^2 \\ = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor-j} \left(2^{\lfloor \log_2 n\rfloor+1}- 2^{\lfloor \log_2 n\rfloor-j}\right)^2 \\ = \frac{18}{16} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor}2^{2\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} (2-2^{-j})^2 \\=\frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} (2-2^{-j})^2.$$ Now the sum term converges to a constant and we have for the upper bound the asymptotics $$\frac{18}{16} \times 7^{\lfloor \log_2 n\rfloor} \times \frac{49}{10} = \frac{441}{80} \times 7^{\lfloor \log_2 n\rfloor}.$$

For a lower bound consider a one digit followed by a string of zeros, which gives $$S(n)\ge \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j 2^{2\lfloor \log_2 n\rfloor} = \frac{18}{16} 2^{2\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor-j} \\ = \frac{18}{16} 2^{2\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} = \frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j}.$$ The sum term once more converges to a constant and we get for the lower bound complexity the asymptotics $$\frac{18}{16}\times 7^{\lfloor \log_2 n\rfloor} \times\frac{7}{3} = \frac{21}{8} \times 7^{\lfloor \log_2 n\rfloor}.$$

Putting the two bounds together we get a complexity of $$S(n) \in \Theta(7^{\lfloor \log_2 n\rfloor}) = \Theta(2^{\log_2 7\times \lfloor \log_2 n\rfloor}) = \Theta(n^{\log_2 7}).$$

This being Strassen the point was to show that the complexity is better than $\Theta(n^3),$ the naive matrix multiplication, which it is, because $\log_2 7 < 3$.

To conclude this calculation we return to $T(n)$ which was supposed to have $T(1)=1$ and not $18/16.$ We can compensate for this by putting $$T(n) = -\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} + S(n).$$ This term only changes the coefficient on the two bounds and does not affect the order of growth.

There are more Master Theorem type calculations at this MSE link.

Addendum. Interestingly if we compute the partial sums for the lower bound we obtain $$-\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} +\frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} = -\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} + \frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \frac{1-4/7\times(4/7)^{\lfloor \log_2 n\rfloor}}{1-4/7} \\= -\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} + \frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \times \frac{7}{3} - \frac{18}{16} \times \frac{4}{3} \times 4^{\lfloor \log_2 n\rfloor} \\ = +\frac{5}{2} 7^{\lfloor \log_2 n\rfloor} - \frac{3}{2} \times 4^{\lfloor \log_2 n\rfloor},$$ which matches up perfectly with the formula that was proposed as an answer in the original question.

$\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.