# Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an array recursively but instead of partitioning the array into two even sub arrays, this time we divide the array into two sub arrays with one containing the first two elements (low, low+1) and the other the rest elements (low+2, high). Here is the pseudo-code of this algorithm:

MAXMIN (A, low, high)
if (high − low + 1 = 2) then
if (A[low] < A[high]) then
max = A[high]; min = A[low].
return((max, min)).
else
max = A[low]; min = A[high].
return((max, min)).
end if
else
(max_l , min_l ) = MAXMIN(A, low, low+1).
(max_r , min_r ) =MAXMIN(A, low+2, high).
end if

Set max to the larger of max_l and max_r ;
Set min to the smaller of min_l and min_r ;

return((max, min))


The classic divide and conquer algorithm as it follows in pseudocode has the following recurrence relation(as given from my textbook):

T(n) = 2, n=2 or n=1 and T(n) = 2T(n/2)+3, n>2


and the pseudocode:

MAXMIN (A, low, high)
if (high − low + 1 = 2) then
if (A[low] < A[high]) then
max = A[high]; min = A[low].
return((max, min)).
else
max = A[low]; min = A[high].
return((max, min)).
end if
else
mid = low+high/2
(max_l , min_l ) = MAXMIN(A, low, mid).
(max_r , min_r ) =MAXMIN(A, mid + 1, high).
end if

Set max to the larger of max_l and max_r ;
Set min to the smaller of min_l and min_r;

return((max, min))


So I came to the conclusion that the recurrence relation of the first algorithm should look something like that:

T(n) = 2, n=2 or n=1 and T(n) = T(2) + T(n-2) + 2


which can also be written as:

T(n) = 2 + T(n-2) + 2 <=> T(n) = T(n-2) + 4.

Is my approach correct or did i miss something? I would be glad if someone could help me out!

P.S.: Sorry for my english!

## closed as unclear what you're asking by David Richerby, Yuval Filmus, Juho, Luke Mathieson, Nicholas MancusoApr 20 '15 at 23:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.