My question concerns the version of the Master Theorem described in CLRS and in this handout.
I already understand the following:
- If the regularity condition in case 3 does not hold, then we can't apply case 3.
- If the regularity condition in case 3 holds then $f(n)=\Omega(n^{\log_ba\ +\ \epsilon})$ is definitely true.
I have two questions:
- Can there be a situation where $f(n)=\Omega(n^{\log_ba\ +\ \epsilon})$ is true but the regularity condition does not hold?
- Why isn't there a regularity condition for cases 1 and 2? Is there a proof that a similar condition is unnecessary (or at least what is the intuition for it being unnecessary in cases 1 and 2)?