Algorithms: Design and Analysis, Part 1 - Exam Question 20

Problem:

Recall the Master Method and its three parameters $a,b,d$. Which of the following is the best interpretation of $b^d$, in the context of divide-and-conquer algorithms?

Solution:

I revisited the lecture video for this one, and now I am explaining in my own words.

The current amount of work is $O(n^d)$.
The problem size become $\frac{n}{b}$, and then the amount of work (for the merge step, ignoring recursive calls is $O((\frac{n}{b})^d)$.

Therefore the amount of work is reduced by a factor of $O(b^d)$, that's why this option is correct.

(Option 1) The rate at which the work-per-subproblem is shrinking (per level of recursion).