How many comparisons are necessary to determine the minimum of a set of n elements?
n-1 comparisions.
It is not difficult to devise an algorithm that can find both the minimum and the maximum of
n elements using Θ(n) comparisons, which is asymptotically optimal. Simply find the
minimum and maximum independently, using n - 1 comparisons for each, for a total of 2n - 2
comparisons.
In fact, at most 3 ⌊n/2⌋ comparisons are sufficient to find both the minimum and the
maximum. The strategy is to maintain the minimum and maximum elements seen thus far.
Rather than processing each element of the input by comparing it against the current
minimum and maximum, at a cost of 2 comparisons per element, we process elements in
pairs. We compare pairs of elements from the input first with each other, and then we
compare the smaller to the current minimum and the larger to the current maximum, at a cost
of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd
or even. If n is odd, we set both the minimum and maximum to the value of the first element,
and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison
on the first 2 elements to determine the initial values of the minimum and maximum, and then
process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3 ⌊n/2⌋
comparisons. If n is even, we perform 1 initial comparison followed by 3(n - 2)/2
comparisons, for a total of 3n/2 - 2. Thus, in either case, the total number of comparisons is at
most 3 ⌊n/2⌋.
n-1 comparisions.
It is not difficult to devise an algorithm that can find both the minimum and the maximum of
n elements using Θ(n) comparisons, which is asymptotically optimal. Simply find the
minimum and maximum independently, using n - 1 comparisons for each, for a total of 2n - 2
comparisons.
In fact, at most 3 ⌊n/2⌋ comparisons are sufficient to find both the minimum and the
maximum. The strategy is to maintain the minimum and maximum elements seen thus far.
Rather than processing each element of the input by comparing it against the current
minimum and maximum, at a cost of 2 comparisons per element, we process elements in
pairs. We compare pairs of elements from the input first with each other, and then we
compare the smaller to the current minimum and the larger to the current maximum, at a cost
of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd
or even. If n is odd, we set both the minimum and maximum to the value of the first element,
and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison
on the first 2 elements to determine the initial values of the minimum and maximum, and then
process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3 ⌊n/2⌋
comparisons. If n is even, we perform 1 initial comparison followed by 3(n - 2)/2
comparisons, for a total of 3n/2 - 2. Thus, in either case, the total number of comparisons is at
most 3 ⌊n/2⌋.
I have written the following algorithm (taking help from CLRS) whose lower-bound is 2*floor(n/2).
ReplyDeleteSimultaneous_Maximum_&_Minimum (A, n)
{
1. If n is even, compare the first two elements and assign the larger to 'max' and
smaller to 'min'. StartIndex = 3.
2. If n is odd, set both 'max' & 'min' to the first element. StartIndex = 2.
3. while i = StartIndex to n
{
if (max < A[i]) {
if (A[i] < A[i+1])
max = A[i+1]; // we confirmed that A[i] or A[i+1] can't be min
else {
max = A[i];
if (min > A[i+1])
min = A[i+1];
}
}
else {
if (min > A[i]) {
if (A[i] > A[i+1])
min = A[i+1]; //confirmed that A[i] or A[i+1] can't be min
else {
min = A[i];
if (max < A[i+1])
max = A[i+1]
}
}
}
i = i + 2; // Update i by 2 (i.e processing elements in pair)
}
}
When Input elements either in increasing order sorted or decreasing order sorted then this algorithm tends give correct output in 2*floor(n/2) running time.
My Ques is: Is this algorithm accepted?
I m extremely sorry my Algo is wrong --- the condition (max > A[i] > min) case doesn't check. So including this checking --- we need 3*floor(n/2) checking.
ReplyDeleteelse { // when max > A[i] and min < A[i]---so A[i] can't be max or min
if (max < A[i+1])
max = A[i+1]
if (min > A[i+1])
min = A[i+1]
}
This modification would sometimes give 4*floor(n/2) -- which is bad. So I am extremely sorry. this algo isn't useful.
I understand the Floor(n/2) but didnot understand the mutification factor 3 while calculating the complexity
ReplyDelete