# Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2

Here is a divide and conquer approach for finding minimum and maximum elements in an array.

MaxMin(i, j, max, min)
{
//max and min are the references so that we can retain their value when
//we return from the function. i and j are the indices of start and
//end respectively.
if (i=j) then max := min := a[i]; //Small(P)
else if (i=j-1) then // Another case of Small(P)
{
if (a[i] < a[j]) then max := a[j]; min := a[i];
else max := a[i]; min := a[j];
}
else
{
// if P is not small, divide P into sub-problems.
// Find where to split the set.
mid := ( i + j )/2;
// Solve the sub-problems.
MaxMin( i, mid, max, min );
MaxMin( mid+1, j, max1, min1 );
// Combine the solutions.
if (max < max1) then max := max1;
if (min > min1) then min := min1;
}


}

If we analyze the complexity of this algorithm, we see that if n is the power of 2, then it does (3n/2)-2 comparisons. My question is how many comparisons does it do if n is not an exact power of 2. I think it does more than 3n comparisons because at the base level, we are left with 3 elements(which take 3 comparisons) instead of 2 elements(which take just 1 comparison). But I am not sure about my thinking. Any help would be appreciated.

• – Anton Trunov Apr 18 '16 at 10:16
• Try to extend the analysis that works for powers of $2$ to general $n$, and see what you get. Also, you can try calculating the number of comparisons for small values of $n$, and then guess the general solution. – Yuval Filmus Apr 18 '16 at 10:31