Unit 7 · Data Structures and Algorithms Paper 2 CS · December 2022 Shift 1

For matrix multiplication using the simple divide-and-conquer algorithm:
A. The running time is T(n) = Θ(n³)
B. The running time is T(n) = Θ(n² log n)
C. The recurrence is T(n) = 8T(n/2) + Θ(n²)
D. The recurrence is T(n) = 8T(2n) + Θ(n² log n)
E. One of the Master theorem cases is applicable
Choose the most appropriate answer from the options given below:

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. A, C, E only

Explanation

Splitting into 8 half-size products plus Θ(n²) additions gives T(n) = 8T(n/2) + Θ(n²). Master theorem case 1 then gives Θ(n^log₂8) = Θ(n³).