What are the time complexities of naive matrix multiplication and Strassen's algorithm?

• A. Naive O(n^2); Strassen O(n^3).
• B. Naive O(n^3); Strassen O(n^3).
• C. Naive O(n^3/2); Strassen O(n^2).
• D. Naive O(n^3); Strassen O(n^log2 7) ≈ O(n^2.807).

Answer: (D)

The main idea is how running time scales as the matrix size grows. For naive matrix multiplication, you truly perform three nested loops over n, giving n^3 scalar multiply-adds. That means the time grows cubically with n.

Strassen’s algorithm reduces the work by dividing the matrices into four n/2 × n/2 blocks and using seven recursive multiplications of those halves (instead of eight in the naive block approach), plus some additions. This leads to a recurrence T(n) = 7 T(n/2) + O(n^2). Solving this with the Master theorem gives T(n) = Theta(n^{log_2 7}) ≈ Theta(n^{2.807}). So Strassen is faster asymptotically than the cubic naive method, though practical performance depends on constants and overhead for smaller matrices.

Therefore, the correct relationship is naive running time O(n^3) and Strassen running time O(n^{log_2 7}) ≈ O(n^{2.807}).