# Using the Master Theorem to solve a recurrence

I have the following recurrence relation, which I am trying to solve using the Master Theorem: $$T(n) = 2T(n/2) + n^{\frac 12} + \log n$$ Comparing the above recurrence to the recurrence of the form:

$$T(n) = aT(n/b) + f(n)$$

We have:

$$a = 2, b = 2, f(n) = n^{\frac 12} + \log n$$

$$n^{\log_ba} = n^{\log_2 2} = n$$

Comparing $$f(n)$$ and $$n^{\log_b a}$$ asymptotically:

$$f(n) = n^{\frac 12} + \log n$$

$$n^{\log_b a} = n$$

Since $$n^{\frac 12}$$ dominates $$\log n$$ in $$f(n)$$, does this mean that the recurrence relation satisfies the first case of the Master Theorem? The first case of the Master Theorem states:

If $$f(n) = O(n^{\log_b a -e})$$, then $$T(n) = Θ(n^{\log_b a})$$ for an $$e > 0$$.

• Are you sure you typed the question right? In your first equation there is no $a$ term. So $\log_2 1= 0$. Mar 12, 2019 at 0:13
• Sorry, the recurrence relation should be 2T(n/2) + n^(1/2) + logn instead. Mar 12, 2019 at 0:25

Yes, what you have is correct: $$\sqrt n + \log(n) \in O(\sqrt n) = O(n^{\log_2 2 - \frac 12})$$ so we are in the first case of the Master theorem.