1
$\begingroup$

Is there a substitution, so that the following recurrence relation can be solved using the given version of the master theorem?

$$ T(n) = 2T(n/2) + \log n $$

Let $a,b \in \mathbb{N}$, where $b > 1$, let $g\colon \mathbb{N} \to \mathbb{N}$ belong to $\Theta(n^c)$, and suppose that

  1. $t(1) = g(1)$.
  2. $t(n) = at(n/b) + g(b)$.

Then the following hold:

  1. If $a < b^c$ then $t(n) \in \Theta(n^c)$.
  2. If $a = b^c$ then $t(n) \in \Theta(n^c\log n)$.
  3. If $a > b^c$ then $t(n) \in \Theta(n^{(\log a)/(\log b)})$.

Considering $S(m) = S(m - 1) + m$ instead of the original recurrence relation turned out to be not very helpful.

$\endgroup$
3
  • $\begingroup$ Your recurrence relation can be solved using the master theorem, in its Wikipedia form. $\endgroup$ Jul 6 at 11:25
  • $\begingroup$ I don't understand what problem is there with directly applying the master's theorem. You don't need to do anything, just apply it. (Apply the statement written in Wikipedia about the master's theorem) $\endgroup$
    – nir shahar
    Jul 6 at 11:37
  • $\begingroup$ The problem is that g(n) := log(n) grows slower than any polynomial and therefore g(n) is not in Θ(n^c). $\endgroup$
    – Philipp
    Jul 6 at 12:26
1
$\begingroup$

Consider the recurrence relation $$ R(n) = 2R(n/2) + g_R(n), \quad g_R(n) = \max(\lceil n^{0.1} \rceil, \lceil \log n \rceil), $$ where $R(1) = T(1)$. Since $g_R(n) = \Theta(n^{0.1})$, case 3 of your theorem implies that $R(n) = \Theta(n)$. Induction shows that $T(n) \leq R(n)$ for all $n$, and so $T(n) = O(n)$.

Similarly, consider the recurrence relation $$ S(n) = 2S(n/2) + g_S(n), \text g_S(n) = \min(1, \lfloor \log n \rfloor), $$ where $S(1) = T(1)$. Since $g_S(n) = \Theta(1)$, case 3 of your theorem implies that $S(n) = \Theta(n)$. Induction shows that $T(n) \geq S(n)$ for all $n$, and so $T(n) = \Omega(n)$.

In total, $T(n) = \Theta(n)$.

$\endgroup$
1
  • $\begingroup$ I tried something similar, but since I had chosen c >= 1, I always ended up in case 2. Thanks for the eye opener! $\endgroup$
    – Philipp
    Jul 6 at 12:37

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.