4.2-6 CLRS

4.2-6[clrs]:

How quickly can you multiply a $kn \times n$ matrix by an $n \times kn$ matrix, using Strassen's algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.

Well, this one was easy. I don't know why I couldn't do it earlier. So,
Case-1:
We want to multiply a $kn \times n$ matrix with a $n \times kn$ matrix. Now we can see that the $kn \times n$ matrix is composed of $k$, $n \times n$ matrices. We can say the same thing for the $n \times kn$ matrix.

Therefore we can rewrite both the matrices as $k \times 1$ and $1 \times k$, by assuming each $n \times n$ matrix as a single element.

Now, if we want to multiply a $k \times 1$ matrix by a $1 \times k$ matrix, then we'll do $k^2$ multiplications, along with no additions. So if  $T(kn \times n,n \times k)$ represents the running times of the multiplication of these two matrices then: $$T(kn \times n,n \times kn) = k^2 T(n \times n,n \times n)+ O(1)$$

And, by Strassen's Algorithm, we know that $T(n \times n,n \times n)= n^{log_2 7}$. Therefore, $$T(kn \times n, n \times kn)=k^2 \times n^{log_2 7}$$

Case-2:
Now, in this case, we want to multiply a $n \times kn$ matrix by a $kn \times n$ matrix. Now again, we'll change them into $1 \times k$ into $k \times 1$ matrices. Notice that this multiplication requires $k$ multiplications of $n \times n$ matrices and $k-1$ additions. Therefore, $$T(n \times kn, kn \times n)= k T(n \times n) +O(k)$$
Which, equals:
$$T(n \times kn,kn \times n) = k \times n^{log_2 7}+O(k) = k \times n^{log_2 7}$$