# Solving $T(n) = 2T(n/2) + \log n$ using the master theorem

Is there a substitution, so that the following recurrence relation can be solved using the given version of the master theorem?

$$T(n) = 2T(n/2) + \log n$$

Let $$a,b \in \mathbb{N}$$, where $$b > 1$$, let $$g\colon \mathbb{N} \to \mathbb{N}$$ belong to $$\Theta(n^c)$$, and suppose that

1. $$t(1) = g(1)$$.
2. $$t(n) = at(n/b) + g(b)$$.

Then the following hold:

1. If $$a < b^c$$ then $$t(n) \in \Theta(n^c)$$.
2. If $$a = b^c$$ then $$t(n) \in \Theta(n^c\log n)$$.
3. If $$a > b^c$$ then $$t(n) \in \Theta(n^{(\log a)/(\log b)})$$.

Considering $$S(m) = S(m - 1) + m$$ instead of the original recurrence relation turned out to be not very helpful.

• Your recurrence relation can be solved using the master theorem, in its Wikipedia form. Jul 6 at 11:25
• I don't understand what problem is there with directly applying the master's theorem. You don't need to do anything, just apply it. (Apply the statement written in Wikipedia about the master's theorem) Jul 6 at 11:37
• The problem is that g(n) := log(n) grows slower than any polynomial and therefore g(n) is not in Θ(n^c). Jul 6 at 12:26

## 1 Answer

Consider the recurrence relation $$R(n) = 2R(n/2) + g_R(n), \quad g_R(n) = \max(\lceil n^{0.1} \rceil, \lceil \log n \rceil),$$ where $$R(1) = T(1)$$. Since $$g_R(n) = \Theta(n^{0.1})$$, case 3 of your theorem implies that $$R(n) = \Theta(n)$$. Induction shows that $$T(n) \leq R(n)$$ for all $$n$$, and so $$T(n) = O(n)$$.

Similarly, consider the recurrence relation $$S(n) = 2S(n/2) + g_S(n), \text g_S(n) = \min(1, \lfloor \log n \rfloor),$$ where $$S(1) = T(1)$$. Since $$g_S(n) = \Theta(1)$$, case 3 of your theorem implies that $$S(n) = \Theta(n)$$. Induction shows that $$T(n) \geq S(n)$$ for all $$n$$, and so $$T(n) = \Omega(n)$$.

In total, $$T(n) = \Theta(n)$$.

• I tried something similar, but since I had chosen c >= 1, I always ended up in case 2. Thanks for the eye opener! Jul 6 at 12:37