Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
"master", not "Master's"
Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

Why is there no regularity condition in case 1 of Master'sthe master theorem?

In case 3 of Master'sthe 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?

Why is there no regularity condition in case 1 of Master's theorem?

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 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?

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?

added 9 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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

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?

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 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?

Source Link
Loading