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.

Example 247

Consider the following recurrence:

\[T(n) = 2T\parens{\frac{n}{2}} + \O(n \log n)\]

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:

\[\begin{split}S(n) \log n &= 2S\parens{\frac{n}{2}}\log{\frac{n}{2}} + \O(n \log n)\\ &= 2S\parens{\frac{n}{2}}(\log n - \log 2) + \O(n \log n)\\ &= 2S\parens{\frac{n}{2}}(\log n - 1) + \O(n \log n)\end{split}\]

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:

\[S(n)\log n \le 2S\parens{\frac{n}{2}}\log n + \O(n \log n)\]

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

\[S(n) \le 2S\parens{\frac{n}{2}} + \O(n)\]

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:

\[S(n) = \O(n \log n)\]

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

\[\begin{split}T(n) &= S(n)\log n = \O(n \log n)\log n\\ &= \O(n \log^2 n)\end{split}\]

Exercise 248

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.