def strassen(A, B): n = len(A) # Base case if n == 1: return A[0][0] * B[0][0] # Divide matrix A into quadrants a11 = A[:n//2][:n//2] a12 = A[:n//2][n//2:] a21 = A[n//2:][:n//2] a22 = A[n//2:][n//2:] # Divide matrix B into quadrants b11 = B[:n//2][:n//2] b12 = B[:n//2][n//2:] b21 = B[n//2:][:n//2] b22 = B[n//2:][n//2:] # Calculate p1 to p7 p1 = strassen(a11, subtract_matrices(b12, b22)) p2 = strassen(add_matrices(a11, a12), b22) p3 = strassen(add_matrices(a21, a22), b11) p4 = strassen(a22, subtract_matrices(b21, b11)) p5 = strassen(add_matrices(a11, a22), add_matrices(b11, b22)) p6 = strassen(subtract_matrices(a12, a22), add_matrices(b21, b22)) p7 = strassen(subtract_matrices(a11, a21), add_matrices(b11, b12)) # Calculate c21, c21, c11, and c22 c12 = add_matrices(p3, p5) c21 = add_matrices(p2, p4) c11 = subtract_matrices(subtract_matrices(add_matrices(p5, p4), p2), p6) c22 = subtract_matrices(subtract_matrices(add_matrices(p1, p2), p3), p7) # Group the results in a single matrix C = [[0 for j in range(n)] for i in range(n)] C[:n//2][:n//2] = c11 C[:n//2][n//2:] = c12 C[n//2:][:n//2] = c21 C[n//2:][n//2:] = c22 return C

O(n)