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$ Commented Mar 12, 2019 at 0:13
  • $\begingroup$ Sorry, the recurrence relation should be 2T(n/2) + n^(1/2) + logn instead. $\endgroup$
    – ceno980
    Commented Mar 12, 2019 at 0:25

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .