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?
[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.