# 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!