# 3.2.1. Selection Algorithm

Problem - Find both the maximum and the minimum elements of a set containing n elements (assume n = 2m for some integer m).

[Aho 2.6]

  begin
    MAX <- any element in S;
    for all other elements x in S do
      if x>MAX then MAX<- x
  end

• T(n) = (n-1) + (n-2) = 2n-3 comparisons

procedure MAXMIN(S):
if |S| = 2 then
  begin
  	let S = {a, b};
  	return (MAX(a,b), MIN(a,b))
  end
else
  begin
  	divide S into two subset S1,S2, each with the half of elements
  	(max1, min1) <- MAXMIN(S1);
  	(max2, min2) <- MAXMIN(S2);
  	return(MAX(max1, max2), MIN(min1, min2))
  end

T(n) = 2T(n/2) + 2 for n > 2, T(n) = 1 for n = 2

→ T(n) = (3/2)n - 2 comparisons

This is the minimum!

The traditional method requires O(n^2) bit operations.

A divide-and-conquer approach

xy = (a2^{\frac n 2} + b)(c2^{\frac n 2} + d) = ac2^n + (ad+bc)2^\frac n 2 + bd

u = (a+b)*(c+d);
v = a*c, w = b*d;
z = v * pow(2,n) + (u-v-w) * pow(2, n/2) + w;

[Aho 2.6]

• T(n) = 1 for n = 1
• T(n) = 3T(n/2) + cn for n > 1 → T(n) = O(nlog3)
• O(n^2) → O(n^{1.59})

Read [Neapolitan 2.6].