A <divide-and-conquer algorithm> \b[divides an input into smaller instances, solves those instances recursively, and combines their answers]. Directly solvable base cases terminate the <recursion>. The total <time complexity> includes both the recursive work and the work of dividing and combining; balanced sizes alone do not determine the running time.

Solution

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 5 / a / Solution

 Solution (source code)