How to find recurrence relation from recursive algorithm

Question

I know how to find recurrence relation from simple recursive algorithms.

For e.g. 
QuickSort(A,LB, UB){
    key = A[LB]
    i = LB
    j = UB + 1
    do{
        do{
            i = i + 1
        }while(A[i] < key)
        do{
            j = j - 1
        }while(A[j] > key)
    if(i < j){
        swap(A[i]<->A[j])
    }while(i <= j)
    swap(key<->A[j]
    QuickSort(A,LB,J-1)
    QuickSort(A,J+1,UB)
}

T(n) = T(n - a) + T(a) + n

In the above recursive algorithm it was quite easy to understand how the input size is reducing after each recursive call. But how to find recurrence relation for any algorithm in general, which is not recursive but might also be iterative. So i started learning how to convert iterative algorithm to recursive just to make it easy to find recurrence relation. I found this link http://refactoring.com/catalog/replaceIterationWithRecursion.html. I used to convert my linear search algorithm to recursive.

LinearSearch(A,x,LB,UB){
    PTR = LB
    while(A[PTR]!=x && PTR<=UB){
        if(PTR==UB+1){
            print("Element does not exist")         
        }
        else{
            print("location"+PTR)
        }
    }
}

got converted to 

LinearSearch(A,x,LB,UB){
PTR=LB
print("Location"+search(A,PTR,UB,x))
}
search(A,PTR,UB,x){
   if(A[PTR]!=x && PTR<=UB){
        if(PTR==UB+1){
            return -1
        }
        else{
            return search(A,PTR+1,UB,x)
        }
    }
    else{
        return PTR
    } 
}

This gives the recurrence relation to be T(n) = T(n-1) + 1

But i was wondering is this the right approach to find recurrence relation for any algorithm? Plus i don't know how to find recurrence relation for algorithms where more than one parameter is increasing or decreasing.

e.g.
unsigned greatest_common_divisor (const unsigned a, const unsigned b)
{
  if (a > b)
  {
    return greatest_common_divisor(a-b, b);
  }
  else if (b > a)
  {
    return greatest_common_divisor(a, b-a);
  }
  else // a == b
  {
    return a;
  }
}

I would suggest you first find the recurrence relation as per your requirement and then develop the algorithm (either iterative like Dynamic Programming, or recursive) rather than the other way round. — Abhishek Bansal, Mar 22 '14 at 04:51
Analysis of algorithms is not a science. There's no way a generic recurrence analysis method is going to determine that the number of recursive calls for `greatest_common_divisor` is roughly the sum of coefficients for the continued fraction representation of a/b. — David Eisenstat, Mar 24 '14 at 17:55

score 1 · Accepted Answer · edited Mar 28 '18 at 00:48

First of all, algorithms are very flexible so you should not expect to have a simple rule that covers all of them.

That said, one thing that I think will be helpful for you is to pay more attention to the structure of the input you pass to your algorithm than to the algorithm yourself. For example, consider that QuickSort you showed in your post. If you glance at those nested do-whiles you are probably going to guess its O(N^2) when in reality its O(N). The real answer is easier to find by looking at the inputs: i always increases and j always decreases and when they finaly meet each other, each of the N indices of the array will have been visited exactly once.

Plus I don't know how to find recurrence relation for algorithms where more than one parameter is increasing or decreasing.

Well, those algorithms are certainly harder than the ones with a single variable. For the euclidean algorithm you used as an example, the complexity is actually not trivial to figure out and it involves thinking about greatest-common-divisors instead of just looking at the source code for the algorithm's implementation.

How to find recurrence relation from recursive algorithm

1 Answers1