Determining a recurrence relation for a given algorithm

Question

void function(int A[], int i, int j){
    if (j == i+1) 
        if (A[i] > A[j])
            swap(A,i,j)
        else {
            int k = (j-i+1)/3;
            function(A,i,j-k); 
            function(A,i+k,j);
            function(A,i,j-k); 
        }
}

This piece of code is taken from a past mid-term exam in my Analysis of algorithms class. It was asked of the students to derive a recurrence relation that describes the behaviour of this function. I've seen a few examples on the internet on how this process is done, but I just can't figure out how to apply it on this particular function, the i and j indexes are really confusing to me.

Any ideas?

Try making a sample array (10 elements or so) and calculate what the actual values of the indexes become. — David
– David, Commented Dec 12, 2015 at 0:50

Saeid · Accepted Answer · 2015-12-11 22:20:40Z

1

Each of the [i,j-k],[i+k,j],[i,j-k] are 2/3 of the [i,j]. So you are dividing your problem to 3 parts when each part is two third of the original size. Therefore your recurrence relation is T(n) = 3*T(n*2/3). You can solve this using Master theorem.

answered Dec 11, 2015 at 22:20

Saeid

4,2617 gold badges30 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Determining a recurrence relation for a given algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related