Problem 5

Recursive algorithm

Design a recursive algorithm called exterma(A, p, r) that finds and returns the ordered pair (min(A[p..r]),

max(A[p..r])). Your algorithm should perform exactly []-2 array comparisons on an input array of

length n.

Problem 5 [Recursive algorithm] continued on next page...

Algorithms

CS 460: Assignment 2

Page 2 of 3

Problem 5

1) Write your algorithm in pseudocode.

2) Prove the correctness of your algorithm by induction on m=r-p+1, the length of the subarray

A[p..r].

3) Write a recurrence for the number of comparisons performed on A[1,..n] and show that T(n) = [1-2

is the solution.