JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (March - 2021 - R16)

The classical matrix multiplication algorithm computes the product of two n x n matrices by calculating each element of the resulting matrix as a dot product of a row and a column. This requires three nested loops, leading to a time complexity of O(n³). Strassen's algorithm uses a divide-and-conquer approach to reduce the number of recursive multiplications from eight to seven. By partitioning the matrices into four sub-matrices and computing seven intermediate products, the recurrence relation becomes T(n) = 7T(n/2) + O(n²). Applying the Master Theorem, this results in a time complexity of O(n^log₂7), which is approximately O(n^2.81).

Strassen's method outperforms the classical approach for large values of n. While Strassen's algorithm has a lower asymptotic complexity, it involves higher constant factors due to the additional matrix additions and subtractions. In practice, the crossover point where Strassen's method becomes more efficient typically occurs when n is between 64 and 128, depending on the specific hardware architecture and implementation details.

Time Complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input. It provides an estimation of the growth rate of the number of operations performed by an algorithm.

The following asymptotic notations are used to represent these complexities:

• Big-O Notation (O): Provides an asymptotic upper bound on the growth rate of a function, representing the worst-case scenario.
• Omega Notation (Ω): Provides an asymptotic lower bound on the growth rate, representing the best-case scenario.
• Theta Notation (Θ): Provides an asymptotic tight bound, where the function is bounded both above and below by the same growth rate, representing the average or exact case.
• Little-o Notation (o): Denotes a loose upper bound, indicating that the growth rate is strictly less than the specified function.
• Little-omega Notation (ω): Denotes a loose lower bound, indicating that the growth rate is strictly greater than the specified function.