What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?ans.O(n3)O(n)O(n2)O(n!) Previous Marked for Review Next

Break Down the Problem

1. We need to determine the time complexity of multiplying two matrices using the Divide and Conquer technique.
2. The problem is essentially a search for the right time complexity from the given options: $O(n^3)$, $O(n)$, $O(n^2)$, or $O(n!)$.

Relevant Concepts

1. Matrix Multiplication: The standard algorithm for multiplying two $n \times n$ matrices involves three nested loops, leading to a time complexity of $O(n^3)$.
2. Divide and Conquer: This method involves breaking down the matrix multiplication into smaller subproblems and combining their results.

Analysis and Detail

1. The matrix multiplication using the Divide and Conquer approach divides each $n \times n$ matrix into four $\frac{n}{2} \times \frac{n}{2}$ matrices.

2. The recurrence relation for the Divide and Conquer matrix multiplication algorithm is given by:

   $T(n) = 8T\left(\frac{n}{2}\right) + O(n^2)$

   Here, $8T\left(\frac{n}{2}\right)$ accounts for the multiplication of four pairs of matrices (each of $\frac{n}{2}$ size), and $O(n^2)$ accounts for the addition of the matrices.

3. Using the Master Theorem to solve this recurrence, we can find that:

   • $a = 8$, $b = 2$, and $f(n) = O(n^2)$.

   We find that $n^{\log_b a} = n^{\log_2 8} = n^3$. Since $f(n) = O(n^2)$ is polynomially smaller than $n^3$, we can use case 1 of the Master Theorem.

Verify and Summarize

1. Thus, the solution to the recurrence relation yields $T(n) = O(n^3)$ for matrix multiplication using the Divide and Conquer method.
2. Therefore, out of the provided choices, the correct option is $O(n^3)$.

Final Answer

The time complexity of matrix multiplication using the Divide and Conquer method is $O(n^3)$.