alleryStart learning →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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.