0
$\begingroup$

The master theorem states that for the general recurrence relation of the form :-

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

Case1: If $f(n)= O(n^{\log_b a - \epsilon })$ for $\epsilon>0$ then, $T(n)=\Theta(n^{\log_b a })$

Case2 If $f(n)= \Theta (n^{\log_b a })$ then $T(n)= \Theta(n^{\log_b a}\log n)$

Case3 If $f(n)= \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon >0$ and regularity condition satisfied then $T(n)= \Theta(f(n))$

I am having trouble understanding the following aspects about it :-

First, it may so happen that case 1 and case 2 both are being satisfied in a situation. For example, $$T(n)=2T(n/2)+n$$ Here $f(n)=n, a=2,b=2, n^{\log_b a}=n$

Here case 1 can be satisfied that is, $f(n)=n=O(n^{1-\epsilon})$ where $\epsilon=0.1$ ( As $ n=O(50 n ^{0.9}) $) then by case 1 the answer should be $\Theta(n^{\log_b a})=\Theta(n^{\log_2 2})=\Theta(n)$ Graph plots of the same: https://www.desmos.com/calculator/hghelfrh7k

Clearly, the graph of $ y=50 x^{0.9} $ is above $ y=x$

Here case 2 satisfies too ie $f(n)= n= \Theta(n^{\log_b a}) = \Theta(n), hence T(n)= \Theta(n\log n)$

As $\Theta()$ represents the asymptotic tight bound, does that mean that $n$ and $n\log n$ are asymptotically equal. I basically want to know what is lacking in my approach.

Also in the recurrence :- $ T(n) =2T(n/2)+ nlogn $

Here a=2,b=2, $n^{log_b a} $= $n$ and $ lim_{n\rightarrow \infty } \frac{nlogn}{n} =\infty $ To show that case 3 of Master theorem is not applicable here, how should I prove nlogn is not polynomially greater than n using limits?

$\endgroup$
1
  • $\begingroup$ Welcome to MSE. Please enclose your MathJax within a pair of $ signs. $\endgroup$ Commented Apr 7, 2018 at 9:41

1 Answer 1

1
$\begingroup$

[The question has changed from under me several times now; I won't keep this answer updated.]

Firstly, your example is the recurrence which describes the time complexity of merge sort, which is well-known to be of order $n \log n$. (In fact, the exact solution to the recurrence is $T(n) = \frac{1}{2} n K + n \log_2(n)$, for any constant $K$.)

In fact I think you simply have two typos. Case 1 should have $\epsilon$ negated, and case 3 should have $\epsilon$ positive. With this statement, Case 3 is clearly not applicable. The three cases do not overlap at all.

$\endgroup$
6
  • $\begingroup$ I am sorry for the formatting inconsistencies. However, I have rectified the problem statement. $\endgroup$ Commented Apr 7, 2018 at 10:07
  • $\begingroup$ Now you are wrong because you said that $n = O(50 n^{0.9})$, which is not true. $\endgroup$ Commented Apr 7, 2018 at 10:10
  • $\begingroup$ The graph that plotted on desmos sketches like this : desmos.com/calculator Does that mean there will a point where graph of n will take over? $\endgroup$ Commented Apr 7, 2018 at 10:14
  • $\begingroup$ Of course. Specifically, $n=97656250000000000$. Naturally, $\lim_{n \to \infty} \frac{n}{50 n^{0.9}} = \lim_{n \to \infty} \frac{1}{50} n^{0.1} = \infty$. $\endgroup$ Commented Apr 7, 2018 at 10:15
  • $\begingroup$ $lim_{n\rightarrow \infty } \frac{ nlogn}{n} =\infty $ -This means nlog n is asyptotically larger than n but how should I show that nlogn is not polynomially larger than n in order to show that case 3 of master theorem cannot be applied there. $\endgroup$ Commented Apr 7, 2018 at 10:25

You must log in to answer this question.

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