Question

How many comparisons are needed to locate the maximum and minimum elements in a sequence with 128 elements using the algorithm in Example 2?

Short answer

Thus, the number of comparisons required is 254.

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms:$\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply Recurrence Relation

The number of comparisons of $n$elements is $f\left(n\right)=2f(n/2)+2$

Also,$f\left(1\right)=0$

We want$f\left(128\right)$

Simply apply the rule:

$$\begin{gathered} f\left(128\right)=2f\left(64\right)+2 \\ f\left(128\right)=2\left(2f\right(32)+2)+2 \\ f\left(128\right)=2\left(2\right(2\left(2\right(2\left(2\right(2f\left(1\right)+2)+2)+2)+2)+2)+2)+2 \\ f\left(128\right)=254 \end{gathered}$$

Thus, the number of comparisons required is 254.