 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability-resit/3/e/ii/solution

Multiplying the recurrence relation by

n

removes the average:

n T (n) = \sum_{i = 0}^{n - 1} T (i) + n^{2} .

For

n \geq 2

, subtract the same identity at

n - 1

n T (n) - (n - 1) T (n - 1) = T (n - 1) + n^{2} - (n - 1)^{2} .

Rearranging gives

T (n) = T (n - 1) + 2 - 1/ n

. This also holds at

n = 1

, because the original recurrence relation gives

T (1) = 1

and

T (0) = 0

. Summing the differences therefore yields

T (n) = 2 n - H_{n} = O (n), H_{n} = \sum_{j = 1}^{n} \frac{1}{j}, H_{0} = 0.

Here

H_{n}

H_{n} \leq n

, we have

n \leq T (n) \leq 2 n

for

n \geq 1

, also establishing

Θ (n)

 New to topics? Read the docs here!