Show that case 3 of the master theorem is overstated, in the sense that the regularity condition \(af(n/b) \leq cf(n)\) for some constant \(c < 1\) implies that there exists a constant \(\epsilon > 0\) such that \(f(n) = \Omega(n^{\log_{b} a + \epsilon})\).

\[\begin{split} af(n/b) & \leq cf(n) \\ \alpha f(n/b) & \leq f(n), \alpha = a/c \\ \alpha f(n) & \leq f(bn) \\ \alpha^{i}f(1) & \leq f(b^{i}) \\ \alpha^{\log_{b}n}f(1) & \leq f(b^{\log_{b}n}) \\ n^{\log_b{\alpha}} & \leq n^{\log_b{a+\epsilon}} \\ n^{\log_b{a} + \log_{b}d} & \leq n^{\log_b{a+\epsilon}}, \alpha = a + d, (c < 1, d > 0) \\ \end{split}\]

Therefore, there exists a constant \(\epsilon = \log_{b}d\) with \(d > 0\) such that \(f(n) = \Omega(n^{\log_{b}a + \epsilon})\).