Question

Show that the worst-case complexity in terms of comparisons of an algorithm that finds the maximum and minimum ofn elements is at least $\mathbf{\lceil }\mathbf{3}\mathit{n}\mathbf{/}\mathbf{2}\mathbf{\rceil }\mathbf{-}\mathbf{2}$.

Short answer

It is proved that Worst case complexity is at least $\lceil 3\mathrm{n}/2\rceil -2$

Step-by-step solution

Consider

Let us consider a list ofnelements. We need to determine the minimum and the

Maximum in the list, which could be any be thenelements. Thus there are2n

possibilities to obtain the actual minimum and maximum, while we need to eliminate

2n-2 of the possibilities to obtain the actual minimum and maximum.

Let us consider two elementsxand y. We will need to comparexand y(check if

$x<y$). when $x<y$ , then we know that x is not the maximum andy is not the

Minimum. when $x\ge y$ then x is not the Minimum and y is not the maximum.

thus we note that we eliminate two possibilities per comparison.

Proof

There are at most$\lceil n/2\rceil$ comparison between two elements that have not been

Compared previously (as we can divide the nelements in at most $\lceil n/2\rceil$ pairs),

which will thus remove at most 2$\lceil n/2\rceil$ comparison.

Since$2n-2$ possibilities need to be eliminated in total, we will then still need to

remove $2n-2-2\lceil n/2\rceil$possibility .

However, we can only remove one such possibility per comparisons(as we compare

The possible maximums to remove one maximum per comparison and we compare

the possible minimums remove on minimum per comparison.

Thus there are then $2n-2-2\lceil n/2\rceil +\lceil n/2\rceil$ comparison in total.

$2n-2-2\lceil n/2\rceil +\lceil n/2\rceil$ = $2n-2-\lceil n/2\rceil$

= $2n-2+\lceil -n/2\rceil$

= $2n+\lceil -n/2\rceil -2$

= $\lceil 2n-n/2\rceil -2$

= $\lceil 3n/2-2\rceil$

Thus we require at most $\lceil 3n/2\rceil -2$comparison to find the maximum and minimum of a list of n elements, which implies that the worst case complexity is at least $\lceil 3n/2\rceil -2$.