For matrix multiplication with a 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 cases of the master theorem applies

1. AA, C, E only
2. BA, D, E only
3. CB, D, E only
4. DB, C, D only

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

Show answer & explanation

Correct answer: A. A, C, E only

Explanation

Splitting into n/2 blocks needs 8 recursive multiplications plus Θ(n²) additions: T(n) = 8T(n/2) + Θ(n²). Since n^(log₂8) = n³ dominates n², master theorem case 1 gives Θ(n³).