Skip to main content
4 of 4
edited tags
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Why is there no regularity condition in case 1 of the master theorem?

In case 3 of the master 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 addition 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?