I'm trying to calculate the exact time complexity for QuickSort's average case. A recurrece relation for quicksort is
T(n) = T(p-1)+T(n-p)+n-1
The average case would then be represented by
T(n) = Σnp=1(1/n (T(p-1)+T(n-p)))+n-1.
Does anyone know how to tackle this equation? I'm not sure of how one could make use of the master theorem or other related mathematical tools to solve this in terms of n.
I do know the final answer must be approximately 1.38 n log(n), but I know not how to get there and I'm interested in the mathematical procedure.
PS: I'm aware questions posted in Stack Overflow should be related to programming. This one might be a bit more mathematical. If it is not appropiate to post this question here, please let me know.