how to find a recurrence relation from algorithm

Viewed 4155

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.

2 Answers
Related