how do you solve this equation of recurrence?
$T(1) = 1$ $T(n) = 2T(\frac{n}{3})+n*log_2(n)+1$
The problem is the term $n*log_2(n)$.
Can I only consider only $n$ as it's the larger then $log_(n)$ and then solve the equations $T(n)=2T(\frac{n}{3})+n+1$?
thanks
On
$$T(1) = 1$$ $$T(n) = 2T\left(\frac{n}{3}\right)+n \log_2(n)+1$$ Assuming that $n=3^m$, for $m\geq 0$, we have $$T\left(3^0\right) = 1$$ $$T\left(3^m\right) = 2T\left(3^{m-1}\right)+3^m \log_2\left(3^m\right)+1$$ After dividing everything by $2^m$, we have $$\frac{T\left(3^0\right)}{2^0}= \frac{1}{2^0}$$ $$\frac{T\left(3^m\right)}{2^m} = \frac{T\left(3^{m-1}\right)}{2^{m-1}}+\frac{3^m \log_2\left(3^m\right)+1}{2^m}$$ Let $S_m=\frac{T\left(3^m\right)}{2^m}$, then $$S_0= 1$$ $$S_m = S_{m-1}+\frac{3^m \log_2\left(3^m\right)+1}{2^m}$$ It follows that $$ S_m=\sum\limits_{k=0}^m \frac{3^k \log_2\left(3^k\right)+1}{2^k} $$
You must be using an impoverished version of the Master Theorem. The wording in Wikipedia, for example, applies to recurrences of the form
$$ T(n) = a T(n/b) + f(n) \qquad\qquad(a\ge 1,b>1) $$
and is perfectly applicable to your case where $f(n) = n\log n+1$. It's not restricted to $f(n)$ being a power of $n$.
The key parameter is $\log_b(a)$, which in your case is $\log_3 2 \approx 1.58$. So to find out which which case of the theorem applies, compare the growth of $n\log n+1$ with the growth of $n^{1.58}$. We find that $$ f(n) = n\log n + 1 = \mathcal O(n^{1+\epsilon}) \qquad\text{and certainly }1+\epsilon < 1.58$$ so the first case of the theorem (in Wikipedia's numbering) applies, and the result is $$ T(n) = \Theta(n^{\log_3 2}) $$