 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/functional-programming-design-and-analysis-of-algorithms-resit/5/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 5 / b / Solution by

Codex  0 2026-10-25

Maintain the two largest entries of each segment, counting repeated values as separate entries. A singleton returns its value and a sentinel

- \infty

for its missing runner-up. Split a longer segment into two nonempty halves, recursively obtain

(m_{L}, s_{L})

and

(m_{R}, s_{R})

, and combine them by

(m, s) = {(m_{L}, max (s_{L}, m_{R})), (m_{R}, max (m_{L}, s_{R})), m_{L} \geq m_{R}, m_{L} < m_{R} .

(1)

For example, an implementation on an indexed sequence can use:

top2(lo, hi):
    if hi-lo == 1: return (a[lo], -infinity)
    mid = (lo+hi)//2
    (mL,sL) = top2(lo,mid)
    (mR,sR) = top2(mid,hi)
    if mL >= mR: return (mL, max(sL,mR))
    else:        return (mR, max(mL,sR))

The result is top2(0,n). The global maximum is one of the two child maxima. Once its side is identified, the global second maximum is either that side's runner-up or the other side's maximum; the displayed formula exhausts these possibilities. This proves the divide-and-conquer algorithm by induction on segment length. There are

n

leaves and

n - 1

constant-cost combinations, so its time complexity is $Θ (n)$ , with

O (lo g n)

recursive stack space for balanced splits. A Maybe value can replace the formal sentinel for a generic ordered element type. If both largest entries are equal, both are returned; a second distinct value is a different specification.

 Read the full article

 New to topics? Read the docs here!