问题描述:

I have been reading about recursion and solving recurrence equations.Came across a term "subtract and conquer". How is it difference from "Divide and conquer" technique.Can i solve these kind of problems using the same techniques used for solving divide and conquer recurrence equations (like master theorem or recursion tree).

"The master theorem applies to divide and conquer algorithms. Some algorithms lead to recurrences of the form T(n) = aT(n-b) + Θ(nd). These might be called "subtract and conquer" or "giant step, baby step" algorithms."

Actually subtract differs from divide, that size of sub problem not divided, but subtracting, everything else is the similar.

Check this link for more details http://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html

I read about "Divide and Conquer" algorithm and came across "Decrease and Conquer" which used Binary Search as its example. So I think "Subtract and Conquer" relates to "Decrease and Conquer" where instead of joining the sub-problems to find the final solution, we find the solution from the sub-problem itself ignoring the remaining part of the original problem.