Question

What is the recurrence relation used in Strassen’s algorithm?

(a) 7T(n/2) + Theta(n^2)

(b) 8T(n/2) + Theta(n^2)

(c) 7T(n/2) + O(n^2)

(d) 8T(n/2) + O(n^2)

This question was addressed to me during an interview for a job.

My enquiry is from Number Theory in division Number Theory of Data Structures & Algorithms II

Answer 1

Right choice is (a) 7T(n/2) + Theta(n^2)

To explain: The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n^2) since there are only 7 recursive multiplications and Theta(n^2) scalar additions and subtractions involved for computing the product.