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).
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).
No comments:
Post a Comment