Is there a way to multiply matrices in lesser than o(n^3) time complexity?

Yes. Divide and conquer method suggests Strassen's matrix multiplication method to be used. If we follow this method, the time complexity is O(n^2.81) times rather O(n^3) times.

Here are some more details about this method.

Suppose we want to multiply two matrices of size N x N: for example A x B = C


[C11 C12] [A11 A12] [B11 B12]
[C21 C22] = [A21 A22] [B21 B22]


Now, this guy called Strassen's somehow :) came up with a bunch of equations to calculate the 4 elements of the resultant matrix


C11 = a11*b11 + a12*b21
C12 = a11*b12 + a12*b22
C21 = a21*b11 + a22*b21
C22 = a21*b12 + a22*b22



If you are aware, the rudimentary matrix multiplication goes something like this


void matrix_mult()
{
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
compute Ci,j;
}
}
}


So, essentially, a 2x2 matrix multiplication can be accomplished using 8 multiplications. And the complexity becomes


2^log 8 =2^3


Strassen showed that 2x2 matrix multiplication can be accomplished in 7 multiplications and 18 additions or subtractions. So now the complexity becomes


2^log7 =2^2.807


This is how he did it


P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11
P3 = A11 * (B12 - B22)
P4 = A22 * (B21 - B11)
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)

C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 - P2 + P6


Now, there is no need to memorize this stuff!