# Supplemental: Algorithms

## Non-master-theorem Recurrences

Recurrences that do not match the pattern required by the master
theorem can often be manipulated to do so using
*substitutions*. We take a look at two examples here.

Consider the following recurrence:

While we solved this recurrence above using the master theorem with log factors, we can also do so through substitution. We perform the substitution \(S(n) = T(n)/\log{n}\) to get the following:

To get this, we substituted \(T(n) = S(n)\log{n}\) and \(T(n/2) = S(n/2)\log(n/2)\) in the first step. Since \(\log n - 1 \le \log n\), we can turn the above into the inequality:

We can then divide out the \(\log n\) from each term to get:

We now have something that is in the right form for applying the master theorem. Even though it is an inequality rather than an equality, because we are computing an upper bound, we can still apply the master theorem. We have \(k/b^d = 2/2^1 = 1\), so we get:

We can then undo the substitution \(S(n) = T(n)/\log{n}\) to get:

In Example 247, we assumed that if \(f(n) = \O(\log n)\), then \(f(n)/\log{n} = \O(1)\). Prove from the definition of big-O that this holds.