Analysis of a specific algorithm running time with recursion

Question

How would I go about calculating the runtime of this algorithm, so I can solve similar questions in the future?

For input size n satisfies the recurrence relation (for n>= 1)

T(n) = (2/n) * (T(0) + T(1) + ... + T(n-1)) + 5n

Answer 1

A way to get rid of sums is to compute differences, after multiplying by $n$ (allow me to write LaTeX, even if this site doesn't use it; I hope the formulas are understandable):

$$ (n + 1) a_{n + 1} - n a_n = 2 a_n + 5 $$

$$ (n + 1) a_{n + 1} - (n + 2) a_n = 5 $$

This is a linear recurrence of the first order. A recurrence of the form:

$$ x_n - u_{n - 1} x_{n - 1} = f_n $$

can be reduced to a sum by dividing by the summing factor $S_n = \prod_{0 \le k \le n} u_n$ to get:

$$ \frac{x_n}{S_n} - \frac{x_{n - 1}}{S_{n - 1}} = \frac{f_n}{S_n} $$

Summing over $1 \le n \le N$ gives a solution to the equation.

In your particular case $S_n = \prod_{0 \le k \le n} \frac{n + 2}{n + 1} = n + 1$, so that:

$$ \frac{a_{k + 1}}{k + 2} - \frac{a_k}{k + 1} = \frac{5}{(k + 1) (k + 2)} $$

\begin{align} \frac{a_n}{n + 1} - \frac{a_0}{1} &= 5 \sum_{0 \le k < n} \frac{1}{(k + 1) (k + 2} \ &= - 5 \sum_{0 \le k < n} \left( \frac{1}{k + 2} - \frac{1}{k + 1} \right) \ &= - 5 \left( \frac{1}{n + 1} - 1 \right) \ &= 5 \frac{n}{n + 1} \end{align}

Finally:

$$ a_n = a_0 (n + 1) + 5 n $$