18k views

### $T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?
6k views

1k views

### Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1 [duplicate]

Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and $T(1)=1$. My attempt: I tried back substituting but I am unable to find a general pattern: \begin{align*} T(n) &=2^2 T(n-2)...