Recurrence Relation for Strassen

Question

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} $$ So I multiplied the $7$ by $2$ several times and the 18n^2^2 several times and ended up with this general equation:- $$ 7k T(n/2^k) + 18n^2k $$ but, well, firstly, is this correct? and also, how do I find the value of k from that beast?!

Many thanks in advance everyone, I really appreciate all your help.

Answer 1

Write $n = 2^k$ and define $U_k = T(2^k)$. The relation beocmes

$$U_k - 7\, U_{k-1} = 18 \cdot 2^{2 k}$$

with the initial condition being

$$U_1 = 1$$

I broke the equation up into a homogeneous solution and an particular solution, then applied the initial condition, as follows:

$$U_k = H_k + P_k$$

$$H_k - 7 H_{k-1} = 0 \implies H_k = A \cdot 7^k$$

Choose $P_k = B \cdot 4^k$; then

$$B \cdot 4^k - \frac{7}{4} B \cdot 4^k = 18 \cdot 4^k \implies B = -24$$

Then $U_k = A \cdot 7^k - 24 \cdot 4^k$. Use $U_1=1$ to get that

$$7 A - 96 = 1 \implies A = \frac{97}{7}$$

The result is

$$U_k =97 \cdot 7^{k-1} -96 \cdot 4^{k-1}$$

To recover $T(n)$, substitute $k=\log_2{n}$ into $U_k$. The result is

$$T(n) = \frac{97}{7} n^{\log_2{7}} - 24 n^2$$

Answer 2

We can actually obtain exact values for $T(n)$ for all values of $n$ and not just powers of two.

Start by working with the alternate recurrence relation $$S(n) = 7 S(\lfloor n/2 \rfloor) + 18n^2$$ where $S(0) = 0.$

Let the binary representation of $n$ be given by $$ n = \sum_{k=0}^{\lfloor \log_2 n\rfloor} d_k 2^k.$$

Then it is not difficult to see that the exact value of $S(n)$ is given by $$ S(n) = 18 \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.$$

Now to get an upper bound on $S(n)$ consider the case where $n$ consists of all one digits, giving $$ S(n) \le 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j \left( \sum_{k=j}^{\lfloor \log_2 n\rfloor} 2^{k-j} \right)^2 = \frac{441}{5} 7^{\lfloor \log_2 n\rfloor}-96 \times 4^{\lfloor \log_2 n\rfloor} + \frac{144}{5} 2^{\lfloor \log_2 n\rfloor} -3.$$ For a lower bound, take $n$ to be a one digit followed by zeros, giving $$ S(n) \ge 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j (2^{\lfloor \log_2 n\rfloor-j})^2 = 42 \times 7^{\lfloor \log_2 n\rfloor} - 24 \times 4^{\lfloor \log_2 n\rfloor}.$$

We still need to account for the fact that $T(0)=1, T(1)=1$ and $T(2)=1.$ A simple calculation shows that $$ T(n) = S(n) - \frac{197}{7} 7^{\lfloor \log_2 n\rfloor} d_{\lfloor \log_2 n\rfloor} + 78 \times 7^{\lfloor \log_2 n\rfloor-1} d_{\lfloor \log_2 n\rfloor-1}.$$ This formula is exact and holds for all $n\ge 3$.

Finally to get the asymptotics look at the two leading terms from the lower and upper bounds. The first is $$\Theta\left(7^{\lfloor \log_2 n\rfloor}\right) = \Theta(2^{\log_2 7 \log_2 n}) = \Theta(n^{\log_2 7}).$$

$T(n)$ fluctuates around this value with the coefficient at most for strings of ones $$\frac{1}{7} \left(\frac{441}{5} - \frac{197}{7} + \frac{78}{7} \right)= \frac{356}{35}$$ and at least $$ 42 - \frac{197}{7} = \frac{97}{7}.$$ The next term in the asymptotic expansion is $$\Theta\left(4^{\lfloor \log_2 n\rfloor}\right) = \Theta(n^2),$$ with the coefficient between $24$ and $96.$