Question

Provide a most efficient divide-and-conquer algorithm for determining the smallest and second smallest values in a given unordered set of numbers. Provide a recurrence equation expressing the time complexity of the algorithm, and derive its exact solution in the number of comparisons. For simplicity, you may assume the size of the problem to be an exact power of a the number 2

Answer 1

Answer:

Check the explanation

Explanation:

Let algorithm be Called minSecondMin(A, p, q) where A is input array with starting index p and ending index q. q-p+1 = n

pseudoCode in C style:-

minSecondMin (A,p,q)// suppose it takes T(n) time

{

if(p +1 == q)

{

if(a[p]>a[q])// here one comparison is done

{

min = a[q]

secondMin = a[p]

}

else

{

min = a[p]

secondMin = a[q]

}

}

else

{

m = floor (p+q/2)

(min1, secondMin1) = minSecondMin (A, p, m)// it takes T(n/2)

(min2, secondMin2) = minSecondMin (A, m+1,q)//it takes T(n/2)

if(min1 > min2)// here 1 comparison

{

min = min2

if(min1>secondMin2)//here 1 comparison

secondMin = secondMin2

else

secondMin = min1

}

else

{

min = min1

if(min2>secondMin1)//here 1 comparison

secondMin = secondMin1

else

secondMin = min2

}

}

}

Recurrence relation for time;-

T(n) = O(1) , if n = 2

= 2T(n/2) + c , if n> 2

Recurrence relation for number of comparisons:-

Let number of comparison = C(n)

Then C(n) = 1 , if n = 2

= 2C(n/2) + 2 , if n > 2

C(n) = 2C(n/2) + 2

Solving using substitution method we get

= 2(2C(n/4) + 2) + 2

= $2^2$C(n/4) + $2^2$ + 2

= $2^3$ C(n/8) + $2^3$ + $2^2$ + 2

Continuing this k times

= $2^k$C(n/$2^k$) + $2^k$ + $2^{k-1$ + $2^{k-2$ + ...+ $2^2$ + 2

It will stop when n/$2^k$= 2 so k = log​​​​2​​​n - 1

= $2^{log_{2}n - 1} C(1) + 2(2^{k-1+1} - 1)$

= $2^{log_{2}(n/2)} + 2^{k+1} - 2$

= $n/2 + 2^{log_{2}n} -2$

= n/2 + n - 2

= 3n/2 - 2

So, required number of comparisons = 3n/2 - 2