JNTU B.Tech III ALGORITHM DESIGN AND ANALYSIS Previous Question Paper (August/September - 2021 - R18)

Traditional matrix multiplication follows the standard row-by-column approach, whereas Strassen’s algorithm utilizes a divide-and-conquer strategy based on block matrices. The primary differences are:

1. Computational Complexity: Traditional multiplication has a time complexity of O(n³), while Strassen’s algorithm improves this to approximately O(n^2.81).
2. Methodology: Traditional multiplication performs 8 multiplications for 2x2 sub-matrices, whereas Strassen’s algorithm reduces this to 7 multiplications by using specific algebraic combinations, trading increased additions for fewer multiplications.

Strassen’s algorithm divides two n x n matrices A and B into four n/2 x n/2 sub-matrices. Instead of the standard 8 recursive multiplications, it computes 7 intermediate products (P1 through P7) using additions and subtractions of sub-matrices. These products are then combined to form the quadrants of the resulting matrix C.

The recurrence relation for the time complexity is:

Applying the Master Theorem where a = 7, b = 2, and f(n) = O(n²):

1. Compare f(n) = n² with n^log_ba = n^log₂7.
2. Since log₂7 ≈ 2.81, we have n² < n^2.81.
3. According to Case 1 of the Master Theorem, the complexity is T(n) = Θ(n^log₂7).

Thus, the time complexity is O(n^2.81), which is asymptotically faster than the traditional O(n³) method for large matrices.

Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively splitting it into two halves, sorting each half, and then merging the sorted halves back together.

The algorithm follows these steps:

1. Divide: Find the middle point of the array to divide it into two subarrays.
2. Conquer: Recursively call Merge Sort on both halves until the base case (an array of size 1) is reached.
3. Combine: Merge the two sorted subarrays into a single sorted array by comparing elements from each subarray and placing the smaller element into the result array.

The efficiency of Merge Sort is determined by the recurrence relation

Complexity analysis:

• Best-case efficiency:
  O(n log n)
  . Even if the array is already sorted, the algorithm still recursively divides the array and performs the merge operations.
• Average-case efficiency:
  O(n log n)
  . The number of comparisons remains consistent regardless of the initial order of elements.
• Worst-case efficiency:
  O(n log n)
  . The depth of the recursion tree is
  log n
  and each level requires
  n
  operations to merge, resulting in a stable performance across all cases.

Merge Sort is a stable sorting algorithm and requires