Divide and Conquer (DAC) approach has three steps at each level of recursion:

1. Divide the problem into number of smaller units called sub-problems.
2. Conquer (Solve) the sub-problems recursively.
3. Combine the solutions of all the sub-problems into a solution for the original problem.

Maximum and Minimum:

1. Let us consider simple problem that can be solved by the divide-and conquer technique.
2. The problem is to find the maximum and minimum value in a set of ‘n’ elements.
3. By comparing numbers of elements, the time complexity of this algorithm can be analyzed.
4. Hence, the time is determined mainly by the total cost of the element comparison.

Explanation:

a. Straight MaxMin requires 2(n-1) element comparisons in the best, average & worst cases.

b. By realizing the comparison of a [i]max is false, improvement in a algorithm can be done.

c. Hence we can replace the contents of the for loop by, If (a [i]> Max) then Max = a [i]; Else if (a [i]< 2(n-1)

d. On the average a[i] is > max half the time, and so, the avg. no. of comparison is 3n/2-1.

A Divide and Conquer Algorithm for this problem would proceed as follows:

a. Let P = (n, a [i],……,a [j]) denote an arbitrary instance of the problem.

b. Here ‘n’ is the no. of elements in the list (a [i],….,a[j]) and we are interested in finding the maximum and minimum of the list.

c. If the list has more than 2 elements, P has to be divided into smaller instances.

d. For example, we might divide ‘P’ into the 2 instances, P1=([n/2],a[1],……..a[n/2]) & P2= ( n-[n/2], a[[n/2]+1],….., a[n]) After having divided ‘P’ into 2 smaller sub problems, we can solve them by recursively invoking the same divide-and-conquer algorithm.

Algorithm:

Example:

Tree Diagram:

i. As shown in figure 4, in this Algorithm, each node has 4 items of information: i, j, max & min.

ii. In figure 4, root node contains 1 & 9 as the values of i& j corresponding to the initial call to MaxMin.

iii. This execution produces 2 new calls to MaxMin, where i& j have the values 1, 5 & 6, 9 respectively & thus split the set into 2 subsets of approximately the same size.

iv. Maximum depth of recursion is 4.

Complexity:

If T(n) represents this no., then the resulting recurrence relations is

T (n)=T([n/2]+T[n/2]+2 $\hspace{1cm}$ n>2

1 $\hspace{4.2cm}$ n=2

1 $\hspace{4.2cm}$ n=1

When ‘n’ is a power of 2, n=2k for some positive integer ‘k’, then

T (n) = 2T(n/2) +2

$\hspace{0.8cm}$ = 2(2T(n/4)+2)+2

$\hspace{0.8cm}$ = 4T(n/4)+4+2

$\hspace{0.8cm}$ *

$\hspace{0.8cm}$ *

$\hspace{0.8cm}$ = 2k-1 T (2) + Σ 1 ≤ I ≤ k-1 ≤ 2i

$\hspace{0.8cm}$ = 2k-1+ 2k - 2

T(n) = (3n/2) – 2

Note that (3n/2) - 2 is the best-average and worst-case no. of comparisons when ‘n’ is a power of 2.