how to write a recurrence relation for a given piece of code

Question

In my algorithm and data structures class we were given a few recurrence relations either to solve or that we can see the complexity of an algorithm.

At first, I thought that the mere purpose of these relations is to jot down the complexity of a recursive divide-and-conquer algorithm. Then I came across a question in the MIT assignments, where one is asked to provide a recurrence relation for an iterative algorithm.

How would I actually come up with a recurrence relation myself, given some code? What are the necessary steps?

Is it actually correct that I can jot down any case i.e. worst, best, average case with such a relation?

Could possibly someone give a simple example on how a piece of code is turned into a recurrence relation?

Cheers, Andrew

Answer 1

Okay, so in algorithm analysis, a recurrence relation is a function relating the amount of work needed to solve a problem of size n to that needed to solve smaller problems (this is closely related to its meaning in math).

For example, consider a Fibonacci function below:

Fib(a) 
{
  if(a==1 || a==0)
    return 1;
  return Fib(a-1) + Fib(a-2);
}

This does three operations (comparison, comparison, addition), and also calls itself recursively. So the recurrence relation is T(n) = 3 + T(n-1) + T(n-2). To solve this, you would use the iterative method: start expanding the terms until you find the pattern. For this example, you would expand T(n-1) to get T(n) = 6 + 2*T(n-2) + T(n-3). Then expand T(n-2) to get T(n) = 12 + 3*T(n-3) + 2*T(n-4). One more time, expand T(n-3) to get T(n) = 21 + 5*T(n-4) + 3*T(n-5). Notice that the coefficient of the first T term is following the Fibonacci numbers, and the constant term is the sum of them times three: looking it up, that is 3*(Fib(n+2)-1). More importantly, we notice that the sequence increases exponentially; that is, the complexity of the algorithm is O(2ⁿ).

Then consider this function for merge sort:

Merge(ary)
{
  ary_start = Merge(ary[0:n/2]);
  ary_end = Merge(ary[n/2:n]);

  return MergeArrays(ary_start, ary_end);
}

This function calls itself on half the input twice, then merges the two halves (using O(n) work). That is, T(n) = T(n/2) + T(n/2) + O(n). To solve recurrence relations of this type, you should use the Master Theorem. By this theorem, this expands to T(n) = O(n log n).

Finally, consider this function to calculate Fibonacci:

Fib2(n)
{
  two = one = 1;
  for(i from 2 to n)
  {
    temp = two + one;
    one = two;
    two = temp;
  }
  return two;
}

This function calls itself no times, and it iterates O(n) times. Therefore, its recurrence relation is T(n) = O(n). This is the case you asked about. It is a special case of recurrence relations with no recurrence; therefore, it is very easy to solve.