In case 3 of Master's theorem,which is applicable when most of the work is being done at the top node(roughly speaking),we also need a regularity condition that the work done at the topmost level is greater than that at the bottom levels,in adition to it being greater than work being done at last level.However,in case 1, which is applicable when most of the work is being done at the last level,we assume that it will be greater than all the previous levels.Why is that? Shouldn't there be a regularity condition for case 1 also?
Why is there no regularity condition in case 1 of Master's theorem?
Ahmad Naseem
- 31
- 2