6

I am trying to understand how the following algorithms works.

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

First, what I am interested in is that in spite of algorithm's working correctly, it is mysterious for me how it finds the maximum element. I will show how I understood this algorithm:

Step 1: we say that in case of an array, l=0 and r=10, it checks if (l>r) which does not hold of course so it calculates m=(0+10)/2;. Then do again the procedure for new bounds. The first pair is (0,5), the second is (6,10) and after the final operation it compares two returned values and finally returns the maximum element between them.

Does this algorithm always work? In each iteration it does not do any comparison, only the final step. How can it determine the maximum element at each recursive iteration? It checks only what. For example: take pair(0,5), is (0 more than 5)? No, so repeat again and divide these bounds into two so get new average value m1=(0+5)/2 then again again and return some element but not the maximum. Also for second subarray we can say the same.

What is the main idea of this algorithm?

Improve this question
7
  • yes i know that it is recursive maximum element search i need only want to understand how it finds maximum i was trying do some work on paper but no result Commented Sep 6, 2011 at 12:56
  • Your question is completely unintelligible. I tried improving it but I don’t really know where to start. Please use paragraphs and proper formatting. Commented Sep 6, 2011 at 12:59
  • @ Konrad Rudolph my question is is it correct that comparision is written at last line? Commented Sep 6, 2011 at 13:00
  • Why do I keep seeing this algorithm on this site? Is it a common learning exercise? It doesn't appear any faster than a linear search... Commented Sep 7, 2011 at 0:04
  • @MooingDuck What is the asymptotic complexity of this algorithm ? Commented Apr 7, 2013 at 8:52

6 Answers 6

Reset to default
7

Your confusion is understandable: the algorithm as written contains a couple of bugs. It accesses memory past the end of a, which is very, very bad. Also, the test whether a range contains only one element is incorrect. If not addressed, this leads to a stack overflow.

The way the maximum function is called suggests that the lower bound is included in the range, but the upper bound is not. a[0] is valid, but a[n] accesses memory past the end of a. When splitting the range, we want the first part to run from l up to but not including m, and the second part to start at m and run up to but not include r. In other words: the "exclusive" upper limit of the first part is equal to the "inclusive" lower limit of the second part. The first internal call to maxsimum is correct. The second internal call should be:

int v=maxsimum(a,m,r);

This leaves us with the problem of detecting a range of length 1. As it stands, the algorithm actually looks for an empty range. The proper test is to look at the difference between the upper and the lower bound:

if (r-l == 1) return a[l];

The complete function is as follows:

int maxsimum(int a[],int l,int r){
   if (r-l==1)  return a[l];
   int m=(l+r)/2;
   int u=maxsimum(a,l,m);
   int v=maxsimum(a,m,r);
   return u>v?u:v;    
}

Now that we have a correct program, the explanation of how this works is straightforward:

  1. If the range contains only one element, then this element is the maximum.
  2. If the range contains more than one element, we split it in two parts. We call the function recursively to compute the maximum of each part. The maximum of these two values is the maximum of the entire range.
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

What is the asymptotic complexity of this algorithm ?
It will O(n) as T(n) = 2T(n/2) + 1
3

The main idea is that if we divide the array in 2 subarrays, then the maximum must be in the left or in the right part of the array; there's no other possibility.

So we find the maximum in the left part, we find the maximum in the right part and the global maximum will obviously be the maximum between the two maximum, that is what is returned by the last line of the maxsimum function.

Improve this answer

2 Comments

thanks for reply i know this i am not asking about what does this algorithm do please i am asking how it determines in each subarray, how it finds maxsimum, comparision is at finall step,so it confuses me
What is it's running time, or asymptotic complexity of this algorithm?
3

Your error is here:

In each iteration it does not do any comparison, only the final step.

This is wrong. In fact, it does a comparison in every step of the recursion (except in the base cases, i.e. where the array size is 1).

Improve this answer

1 Comment

ok thanks @Konrad Rudolph thanks for reply i will try to understand more deeply
1

Let me comment the maximum part of the code for you, and try not to add confusion:

if (l==r)  return a[l]; //trivial case, if there is only one value in the array return it
int m=(l+r)/2; //find value halfway into the array
int u=maxsimum(a,l,m); //find the maximum value for the lower part of the array
int v=maxsimum(a,m+1,r); //find the maximum value for the top part of the array
return u>v?u:v; //return the highest value of them.

So the array 0..10 is splitted into 0..5 and 6..10 and passed into the same function. Only when there is only one value the recursion ends and that single value is passed to their callees. Then in the second lowest cases, like value a[0] and a[1] it will do the first comparisons. The results of these will be passed up to the higher cases until it will exit the function for the final time returning with the largest value of all the cases.

I hope was able clarify a bit for you.

Improve this answer

Comments

1

Error in main() function, test array has 10 elements, should be:

cout << maxsimum(a,0,n-1) << endl;
Improve this answer

Comments

1

This answer might be so late, but it may be useful to someone to grasp the recursion calls, I modified the above code to trace out the function calls. After seeing the output it is easy to see how a recursive tree is made.

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
if (l == r)  
    return a[l];
int m = (l+r)/2;

cout<<"values gonna get computed in 1st recursive call"<< l<<" "<< m<<"\n";
int u = maxsimum(a,l,m);

cout<<"value of u "<<u<<"\n";

cout<<"value gonna get computed in 2nd recursion  call "<<m+1 <<" "<<r<<"\n";
int v = maxsimum(a,m+1,r);

cout<<"value of v : "<<v<<"\n";
cout<<"current u value :"<<u <<"current v value "<<v <<"\n";

return u>v?u:v;    
}

int main() {
int a[] = {5,6,7,8,9};
int n = sizeof(a)/sizeof(int);
cout << maxsimum(a,0,n-1) << endl;         
return 0;
}

Here is the recursion tree for the above program, the tree first goes towards the left side i.e for the first recursive statement, then each call returns its base value, the return condition makes sure only the maximum element is selected in each calls.

                 (9)  
                (0,4)
              /      \
           7 /        \9
        (0,2)          (3,4)
         /  \          /    \
       6/    \7      8/      \9
       (0,1)  (2,2)  (3,3)     (4,4) 
        / \      
      5/   \6
     (0,0) (1,1)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.