Using the Master Theorem to solve a recurrence

Question

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$.

Answer 1

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.