# Finding the recurrence from an algorithm

1. Oct 22, 2008

### Gear2d

I need some help. I am having a hard time find the recurrence when given an algorithm in c++. The algorithm is a Max search: Its where the program goes through the array from first element to last, or last to first (depends on how you program it) to look for the largest value. In this case it says if you give the program n elements (1.......n), the program goes from (0....n-1) because array indexing starts from 0 until n-1. So say you have:
1 2 3 4 5 6, and you want the element at A[0], you get 1, say A[5] = 6, and so on. Here is the algorithm goes n-1 to 0, and where "A" is the array:

Algorithm recursiveMax(A,n)
Input: Array A storing n>= 1 integers
Output: The Maximum element in A

if n = 1 then //if there is only 1 element in array
return A[0]

else
return max{recursiveMax(A,n-1), A[n-1]}

The book says the recurrence is:

f(n) = 3 when n=1 and f(n-1) + 7 otherwise

Now I understand where the three is coming from, its when you have the best case where there is only 1 element in the array so it preforms 3 steps too do the program. But how about the second part?

2. Oct 23, 2008

### HallsofIvy

Since there is no "f" any where in what you say previous to "f(n)= 3 ..." and it clearly is not the output of the algorithm, I don't see how any one can figure that out! What is f supposed to measure?