Question

The problem solving technique which divides a problem into smaller sub problems and then combines their results _________

• A. Greedy
• B. Backtracking
• C. Divide and conquer
• D. Brute force

Hint:

Classic examples of this technique include Merge Sort, Quick Sort, and Strassen's Matrix Multiplication. It often leads to efficient $O(n \log n)$ time complexities.

Answer 1

The Correct Option is C

Concept: Divide and Conquer is a fundamental algorithmic paradigm based on multi-branched recursion.
• Divide: Breakdown the problem into smaller sub-problems of the same type.
• Conquer: Solve these sub-problems recursively. If they are small enough, solve them directly.
• Combine: Merge the solutions of the sub-problems to create the solution for the original problem.

Step 1: Analyzing the multi-step process.
The key characteristic is the recursive decomposition of a task. By breaking a large problem into manageable chunks, we reduce complexity.

Step 2: Evaluating alternative techniques.
Greedy (A) makes the best local choice at each step without looking back. Backtracking (B) explores all possibilities and prunes the search tree. Brute Force (D) tries every single possible solution without optimization.

Step 3: Conclusion based on "Divide" and "Combine".
The specific mention of "combining results" is the hallmark of Divide and Conquer. Therefore, Option (C) is the technically accurate definition.