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