 Solution

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

n^{2}

. Since

1/4 \leq m / n \leq 1/2

m^{2} + (n - m)^{2} \leq \frac{5}{8} n^{2} .

Choose

C \geq max {T (1), 8/3}

T (j) \leq C j^{2}

. Both child sizes are positive and less than

n

, so

T (n) \leq C {m^{2} + (n - m)^{2}} + n^{2} \leq (\frac{5}{8} C + 1) n^{2} \leq C n^{2} .

The same factor

5/8

occurs for the exact fractional split. Therefore

T (n) = O (n^{2})

 New to topics? Read the docs here!