1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.