Lesson 4

Now we are ready to generalize this idea.

Theorem. If \(T(n)=aT(n/b)+O(n^{d})\) for constants \(a>0\), \(b>1\), and \(d \ge 0\), then \[T(n)= \begin{cases}O(n^{\log_b a}) & \text{if \(\ \log_{b}a>d\),}\\ O(n^d\log n) & \text{if \(\ \log_{b}a=d\),}\\ O(n^d) & \text{if \(\ \log_{b}a<d\),}\end{cases}\]

Thus, to determine the growth rate of \(T(n)\), it suffices to compare the values of \(\log_{b} a\) and \(d\) (which is equivalent to comparing \(a\) and \(b^{d}\)).