Question

Recursive algorithm like Merge Sort cannot use Dynamic Programming because:

• A. The subproblems of merge sort are not overlapping in any way
• B. Dynamic programming will not handle recursion
• C. Dynamic programming takes a very long time and will not give an optimal solution
• D. Sorting cannot be handled by dynamic programming

Hint:

A problem is suited for dynamic programming only if it has:
1. Overlapping Subproblems – solved multiple times.
2. Optimal Substructure – optimal solutions built from optimal subproblem solutions. Since Merge Sort does not have overlapping subproblems, it cannot use DP.

Answer 1

The Correct Option is A

Step 1: Understanding Merge Sort
- Merge Sort is a divide-and-conquer algorithm.
- It splits an array into two halves, recursively sorts each half, and then merges them back together.
Step 2: Why Merge Sort Cannot Use Dynamic Programming?
- Dynamic Programming (DP) requires overlapping subproblems and optimal substructure.
- Overlapping Subproblems: A problem has overlapping subproblems if it solves the same subproblems multiple times.
- Optimal Substructure: A problem has optimal substructure if an optimal solution to the problem can be constructed from the optimal solutions of its subproblems.
- Merge Sort does not have overlapping subproblems, because:
- Each recursive call sorts a completely different part of the array.
- It does not reuse solutions to the same subproblems.
Step 3: Evaluating the Options
- (A) Correct: Merge Sort does not have overlapping subproblems, making it unsuitable for DP.
- (B) Incorrect: DP can handle recursion, as seen in Fibonacci and matrix chain multiplication.
- (C) Incorrect: DP does not necessarily take longer and often provides optimal solutions.
- (D) Incorrect: Some sorting problems can be solved using DP, such as optimal binary search tree construction.