retagged by
8,000 views
19 votes
19 votes

For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers:

$$T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$$ Which one of the following options is correct about the recurrence $T(n)$?

  1. If $f(n)$ is $n \log_2(n)$, then $T(n)$ is $\Theta(n \log_2(n))$
  2. If $f(n)$ is $\dfrac{n}{\log_2(n)}$, then $T(n)$ is $\Theta(\log_2(n))$
  3. If $f(n)$ is $O(n^{\log_b(a)-\epsilon})$ for some $\epsilon >0$, then $T(n)$ is $\Theta(n^{\log_b(a)})$
  4. If $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$
retagged by

3 Answers

Best answer
24 votes
24 votes

Options A and B are definitely wrong, condition on $f(n)$ can’t be independent of $a$ and $b$ in any case, it should take both $a$ and $b$ into account.

Option C is correct. standard case of master theorem, if $f(n)$ is polynomial time smaller than $O(n^{\log_ba})$, then $T(n) = \Theta(n^{\log_ba})$.  (see case $1$ below).

$\textbf{Theorem 4.1 (Master theorem)}$

Let $a \geq 1$ and $b>1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence

$$T(n) = aT(n/b) + f(n),$$

where we interpret $n/b$ to mean either $\left \lfloor n/b \right \rfloor$ or $\left \lceil n/b \right \rceil.$ Then $T(n)$ has the following asymptotic bounds:

  1. If $f(n) = O(n^{\log_{b}a-\varepsilon})$ for some constant $\varepsilon >0,$ then $T(n) = \Theta (n^{\log_{b}a}).$
  2. If $f(n) = \Theta (n^{\log_{b}a}),$ then $T(n) = \Theta(n^{\log_{b}a}\lg n).$
  3. If $f(n) = \Omega(n^{\log_{b}a+\varepsilon})$ for some constant $\varepsilon > 0,$ and if $af(n/b)\leq cf(n)$ for some constant $c < 1$ and all sufficiently large $n,$ then $T(n) = \Theta (f(n)).$

Reference

Option D is wrong,  (see case $2$ above).

A good slide to understand master theorem and the idea behind it.

edited by
0 votes
0 votes
In recurrence relation $f\left ( n \right )$ means extra time other than the time taken by smaller problem .

So, We can say that the Total time

$T\left ( n \right )=$ Time taken by smaller problem +  Any other extra Time

With this, we can conclude the following relation

$T\left ( n \right ) $  $\geq $ $f\left ( n \right )$

And, above equation is only satisfied in option C.
edited by
Answer:

Related questions