Question

What is the running time of Strassen’s algorithm for matrix multiplication?

(a) O(n^2.81)

(b) O(n^3)

(c) O(n^1.8)

(d) O(n^2)

I got this question during an interview.

I want to ask this question from Number Theory in chapter Number Theory of Data Structures & Algorithms II

Answer 1

Correct answer is (a) O(n^2.81)

The best explanation: Strassen’s matrix algorithm requires only 7 recursive multiplications of n/2 x n/2 matrix and Theta(n^2) scalar additions and subtractions yielding the running time as O(n^2.81).