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?