Solve recurrence relations
This is similar to the recurrence arising in the analysis of Quicksort, search for "quicksort analysis" to get lots of results.

An easy road is to write:
\begin{align}
(n + 1) T(n + 1) &amp;= 2 \sum_{0 \le k \le n} T(k) + (n + 1) c \\
n T(n)           &amp;= 2 \sum_{0 \le k \le n - 1} T(k) + n c
\end{align}
Subtract to get:
$$
(n + 1) T(n + 1) - (n + 2) T(n) = c
$$
This is a linear recurrence of the first order. Divide by $(n + 1) (n + 2)$ to get:
\begin{align}
\frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1}
  &amp;= \frac{c}{(n + 1) (n + 2)} \\
\sum_{0 \le k \le n - 1}
    \left( \frac{T(k + 1)}{k + 2} - \frac{T(k)}{k + 1} \right)
  &amp;= c \sum_{0 \le k \le n - 1} \frac{1}{(k + 1) (k + 2)} \\
\frac{T(n)}{n + 1} - T(0)
  &amp;= c \sum_{1 \le k \le n} \left( \frac{1}{k} - \frac{1}{k + 1} \right) \\
  &amp;= c \left( 1 - \frac{1}{n + 1} \right) \\
  &amp;= c \frac{n}{n + 1} \\
T(n)
  &amp;= T(0) (n + 1) + c n
\end{align}