Suppose a special recurrence relation for quicksort is: $T(0)=\Theta(1)$ (N>0) $T(N)= T(N-1)+T(0)+\Theta(\sqrt{N}) $
How does this relate to the theta class of: $\Theta(N \sqrt{N})$ ? Can someone please help me understand why this takes place and the steps it takes to get their?
If $T(N)= T(N-1)+T(0)+\Theta(\sqrt{N}) $, then there are positive constants $a$ and $b$ such that $a\sqrt{n} <T(n)- T(n-1)-T(0) < b \sqrt{n} $.
Summing this from $n=2$ to $m$, $\sum_{n=2}^{m} a\sqrt{n} <\sum_{n=2}^{m} (T(n)- T(n-1)-T(0)) < \sum_{n=2}^{m} b \sqrt{n} $, and, since $\sum_{n=2}^{m} \sqrt{n} \approx \frac12 m^{3/2} $, we get $ T(m)-T(1)-(m-1)T(0) =\Theta(m^{3/2}) $ or $ T(m) =\Theta(m^{3/2}) $.
