Algorithm with ceil(n/2) comparisons

[evinda]

Hello! (Wave)

I am looking at the following exercise:

We say that a sequence of numbers $A=(a_1,a_2, \dots, a_n) , n \geq 3$, is strictly alternating if for each $i$, with $2 \leq i \leq n-1$, one of the following conditions stands:

• $a_{i-1}< a_i$ and $a_i>a_{i+1}$
  $$$$
• $a_{i-1}>a_i$ and $a_i<a_{i+1}$

For example, the sequences $(2,10,5,6,3,11,-1,7,4)$ and $(2,-7,4,3,6,0,33,2)$ are alternating, but the sequnce $(5,6,7,3,4,-2,7,10)$ isn't.

Design an algorithm, that, given an alternating sequence of numbers $A$, executes at most $\lceil \frac{n}{2} \rceil$ comparisons, in order to calculate the minimum element of $A$. Justify your answer.

I wrote the following code:

#include <stdio.h>

int main()
{
int n,i,min,position_min;
printf("Give n: \n");
scanf("%d",&n);
while (n<3){
   printf("	Give an other value for n: \n");
   scanf("%d", &n);
}
int A[n];
for (i=0; i<n; i++){
     printf("Give the value of the %dth position of the array: \n",i+1);
     scanf("%d",&A[i]);
}
min=A[0];
position_min=0;
if (A[1]<min) {
    min=A[1];
    position_min=1;
}
for (i=position_min+2; i<n; i+=2){
    if (A[i]<min){
       min=A[i];
       position_min=i;
    }
}
printf("min=%d \n ",min);
return 0;
}

So, we need $2 \left ( \frac{n-\text{position_min}-2+1}{2} \right )=n-\text{position_min}-1$ comparisons..But.. we don't need $\lceil \frac{n}{2} \rceil$ comparisons, at the algorithm I wrote.. (Sweating)

How could I do it otherwise?

 

[alyafey22]

If the first number is smaller than the second then you have the indecies are even. Otherwise they are odd.

You don't need to store the value of the element but rather you store the index.

For example :

A = {4,6,5,7,3,8,2}  
Then min is initialized to 0 since 4 <6.  counter =2;
Since A[min]<A[counter] , min stays 0;
Counter = counter+2 = 4;
Since A[min]>A[counter] min=4;
Counter = counter+2=6;
Since A[min]>A[counter] min=6;
Counter = counter+2=8 > length(A)
Hence min = 6 and the minimum is A[6]=2;

Since each time we travel almost to the end of the array and we skip one element at a time we expect the complexity to be $$\frac{n}{2}$$.Fore the case were the first element is greater than the second initialize min=1 and counter = 3.

 

[evinda]

If the first number is smaller than the second then you have the indecies are even. Otherwise they are odd.

You don't need to store the value of the element but rather you store the index.

For example :

A = {4,6,5,7,3,8,2}  
Then min is initialized to 0 since 4 <6.  counter =2;
Since A[min]<A[counter] , min stays 0;
Counter = counter+2 = 4;
Since A[min]>A[counter] min=4;
Counter = counter+2=6;
Since A[min]>A[counter] min=6;
Counter = counter+2=8 > length(A)
Hence min = 6 and the minimum is A[6]=2;

Since each time we travel almost to the end of the array and we skip one element at a time we expect the complexity to be $$\frac{n}{2}$$.Fore the case were the first element is greater than the second initialize min=1 and counter = 3.

So, at this for loop:

for (i=position_min+2; i<n; i+=2){
    if (A[i]<min){
       min=A[i];
       position_min=i;
    }
}

we don't need to write the command:

position_min=i;

, right? (Thinking)

So,should it be like that?

#include <stdio.h>

int main()
{
int n,i,min,j;
printf("Give n: \n");
scanf("%d",&n);
while (n<3){
   printf("	Give an other value for n: \n");
   scanf("%d", &n);
}
int A[n];
for (i=0; i<n; i++){
     printf("Give the value of the %dth position of the array: \n",i+1);
     scanf("%d",&A[i]);
}
min=A[0];
j=0;
if (A[1]<min) {
    min=A[1];
    j=1;
}
for (i=j+2; i<n; i+=2){
    if (A[i]<min){
       min=A[i];
    }
}
printf("min=%d \n ",min);
return 0;
}

 

[alyafey22]

Generally we are not interested in the element but rather the index so we have

if(A[0] < A[1])
    min=0;
else
    min=1;

for(counter = min+2; counter < n ; counter+=2)
    if(A[counter] < A[min])
          min = counter;

printf("The minimum is %d ", A[min]);

 

[evinda]

Generally we are not interested in the element but rather the index so we have

if(A[0] < A[1])
    min=0;
else
    min=1;

for(counter = min+2; counter < n ; counter+=2)
    if(A[counter] < A[min])
          min = counter;

printf("The minimum is %d ", A[min]);

So, we need $n-min-2+1=n-min-1=\left\{\begin{matrix}
\frac{n-1}{2} &, min=0 \\
\\
\frac{n-2}{2} & ,min=1
\end{matrix}\right.$ comparisons, right? (Thinking)

But.. how can we show that we need $ \lceil \frac{n}{2} \rceil$ comparisons?

 

[Nono713]

Just don't bother only checking the last element if min = 0, do it every time. It doesn't affect correctness, and makes your code simpler to analyze, because in that case you simply have this number of comparisons:

$$1 + \left ( \left \lfloor \frac{n}{2} \right \rfloor - 1 \right ) + (n \bmod 2) = \left \lfloor \frac{n}{2} \right \rfloor + (n \bmod 2)$$

Where the first $1$ is the initial comparison, the second term is the for loop (note that you must subtract $1$ because you've already processed the first two elements) and the final $n \bmod 2$ is because we need one more comparison if $n$ is odd for the last element.

If $n$ is even, then this gives:

$$\frac{n}{2} = \left \lceil \frac{n}{2} \right \rceil$$

And if $n$ is odd, then this gives:

$$\frac{n - 1}{2} + 1 = \frac{n + 1}{2} = \left \lceil \frac{n}{2} \right \rceil$$

And so you are done. Sometimes it pays off to not be too clever :)