Solve recurrence relations

A) Solve this recurrence where $T(0)=0$ and write it in O-notation:
$T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$

So, I started to calculate:


$T(1)=2(0)+c=c$


$T(2)=1(0+c)+c=2c$

and so on, which gives me that $T(n)=nc$

This I can prove by induction: $(n-1) \rightarrow n$


$T(n)= {2 \over n} (0+c+2c+...+(n-1)c)+c = {2 \over n} (c{(n-1)n \over
2} )+c = nc$

Which gives me $O(n)$ (since $c$ is a constant). Am I right with this?


B) For $T(n)=kT({n \over k})+ckn$
find the closed form for the function $T(n)=f(c,k,n)$ (I don't know what does this mean) and write it in
$\mathcal O$-notation. If you had the algorithm working with $k=2$, $k=3$ or
$k=4$ which one would you choose?

I'm stuck with this problem. With the help of the master theorem, I would get $log_k k = 1$ which would give $\mathcal O(n \log n)$ but how to find the closed form?

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) &= 2 \sum_{0 \le k \le n} T(k) + (n + 1) c \\
n T(n) &= 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}
&= \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)
&= c \sum_{0 \le k \le n - 1} \frac{1}{(k + 1) (k + 2)} \\
\frac{T(n)}{n + 1} - T(0)
&= c \sum_{1 \le k \le n} \left( \frac{1}{k} - \frac{1}{k + 1} \right) \\
&= c \left( 1 - \frac{1}{n + 1} \right) \\
&= c \frac{n}{n + 1} \\
T(n)
&= T(0) (n + 1) + c n
\end{align}

StackExchange Computer Science Q#27705, answer score: 6