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$ Apr 7 '18 at 9:41
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$ Apr 7 '18 at 10:07
  • $\begingroup$ Now you are wrong because you said that $n = O(50 n^{0.9})$, which is not true. $\endgroup$ Apr 7 '18 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$ Apr 7 '18 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$ Apr 7 '18 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$ Apr 7 '18 at 10:25

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.