how to find a recurrence relation from algorithm

Question

I'm trying to understand recurrence relations. I've found a way to determine the maximum element in an array of integers through recursion. Below is the function. The first time it is called, n is the size of the array.

int ArrayMax(int array[], int n) {
    if(n == 1)
        return array[0];
    int result = ArrayMax(array, n-1);
    if(array[n-1] > result)
        return array[n-1];
    else
        return result;
}

Now I want to understand the recurrence relation and how to get to big-O notation from there. I know that T(n) = aT(n/b) + f(n), but I don't see how to get what a and b should be.

Answer 1

a is "how many recursive calls there are", and b is "how many pieces you split the data into", intuitively. Note that the parameter inside the recursive call doesn't have to be n divided by something, in general it's any function of n that describes how the magnitude of your data has been changed.

For example binary search does one recursive call at each layer, splits the data into 2, and does constant work at each layer, so it has T(n) = T(n/2) + c. Merge sort splits the data in two each time (the split taking work proportional to n) and recurses on both subarrays - so you get T(n) = 2T(n/2) + cn.

In your example, you'd have T(n) = T(n-1) + c, as you're making one recursive call and "splitting the data" by reducing its size by 1 each time.

To get the big O notation from this, you just make substitutions or expand. With your example it's easy:

T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c = ... = T(0) + nc

If you assume T(0) = c0, some "base constant", then you get T(n) = nc + c0, which means the work done is in O(n).

The binary search example is similar, but you've got to make a substitution - try letting n = 2^m, and see where you can get with it. Finally, deriving the big O notation of eg. T(n) = T(sqrt(n)) + c is a really cool exercise.

Edit: There are other ways to solve recurrence relations - the Master Theorem is a standard method. But the proof isn't particularly nice and the above method works for every recurrence I've ever applied it to. And... well, it's just more fun than plugging values into a formula.