Divide-and-Conquer

Question 1

In recursion, what is ‘recursive case’, and what is ‘base case’.

Answer 1

When the subproblems are large enough to solve recursively, we call that the ‘recursive case’. Once the subproblems become small enough that we no longer recurse, we say that is ‘base case’.

Question 2

What are the methods for obtaining asymptotic Big Theta or Big O bounds on the divide-and-conquer solutions?

Answer 2

• Substitution method - guess a bound and then use mathematical induction to prove the guess correct.
• Recursions-tree method - convert the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion.
• The Master method - provides bounds for recurrences of the form: T(n) = aT(n/b) + f(n)

Question 3

Name few examples of problems which can be solved using divide-and-conquer approach.

Answer 3

• Sorting
• Maximum subarray
• Matrix multiplication
• …