1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – David Richerby Apr 18 '15 at 10:02
  • $\begingroup$ By the way, your English is excellent -- no need to apologise for anything! $\endgroup$ – David Richerby Apr 18 '15 at 10:02