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$

closed as unclear what you're asking by David Richerby, Yuval Filmus, Juho, Luke Mathieson, Nicholas Mancuso Apr 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.

  • 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