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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Your recurrence relation can be solved using the master theorem, in its Wikipedia form. $\endgroup$ Commented Jul 6, 2021 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$ Commented Jul 6, 2021 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$ Commented Jul 6, 2021 at 12:26

1 Answer 1

Reset to default
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)$.

Improve this answer
$\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$ Commented Jul 6, 2021 at 12:37

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.