Per the lecture, Strassen's algorithm for n×n matrix multiplication obeys
AT(n) = 7T(n/2) + Θ(n²), giving O(n^log_2 7) ≈ O(n^2.81)
BT(n) = 8T(n/2) + Θ(n²), giving the naive O(n³)
CT(n) = T(n/2) + Θ(n²), giving O(n²)
DT(n) = 2T(n/2) + Θ(n), giving O(n log n)
Answer & Solution
Correct answer: A. T(n) = 7T(n/2) + Θ(n²), giving O(n^log_2 7) ≈ O(n^2.81)
Naive matrix multiplication splits two n×n matrices into eight n/2 × n/2 blocks (8T(n/2)+n²) and gives O(n³). Strassen cleverly reduces 8 sub-products to 7, hence 7T(n/2)+Θ(n²), giving O(n^log_2 7) ≈ O(n^2.81). It is the original sub-cubic matrix multiply.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for