Min and max. Given an array of N elements, find the min and max using as few compares as possible. Brute force: find the max (N-1 compares), then find the min of the remaining elements (N-2 compares).
Solution 1. Divide and conquer: find min and max in each half (2T(N/2) compares), return min of 2 and max of 2 (2 compares). T(1) = 0, T(2) = 1, T(N) = 2T(N/2) + 2. Recurrence solution: T(N) = ceil(3N/2) - 2.
Solution 2. Divide the elements into pairs and compare two elements in each pair. Put the smallest elements in A and the largest in B. If n is odd, put element n in both A and B. This requires floor(n/2) comparisons. Now directly compute the minimum in A (ceil(n/2) - 1 comparisons) and the maximum in B (ceil(N/2) - 1) comparisons. [In fact, this is best possible.]
LChars:= LChars + Stroka[i];Include(LChars, Stroka[i]);LChars:= LChars + [Stroka[i]];