Counting primitive operations on recursive functions

Question

I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given algorithm. Everything was clear to me until the moment they showed a recursive function (a simple recursive way to calculate the maximum value of an array) and its primitive operation count.

The function (in pseudo-code) is this:

Algorithm recursiveMax(A, n):
    Input: An array A storing n ≥ 1 integers.
    Output: The maximum element in A.
    
    if n = 1 then
        return A[0]
    return max{recursiveMax(A, n − 1), A[n − 1]}

where A is an array and n its length. The author states what follows concerning how we calculate the number of primitive operations this function has:

As with this example, recursive algorithms are often quite elegant. Analyzing the running time of a recursive algorithm takes a bit of additional work, however. In particular, to analyze such a running time, we use a recurrence equation, which defines mathematical statements that the running time of a recursive algorithm must satisfy. We introduce a function T (n) that denotes the running time of the algorithm on an input of size n, and we write equations that T (n) must satisfy. For example, we can characterize the running time, T (n), of the recursiveMax algorithm as T(n) = 3 if n = 1 or T(n - 1) + 7 otherwise, assuming that we count each comparison, array reference, recursive call, max calculation, or return as a single primitive operation. Ideally, we would like to characterize a recurrence equation like that above in closed form, where no references to the function T appear on the righthand side. For the recursiveMax algorithm, it isn’t too hard to see that a closed form would be T (n) = 7(n − 1) + 3 = 7n − 4.

I can clearly understand that in the case of a single item array, our T(n) would be just 3 (only 3 primitive operations will occur, i.e. the comparision n = 1, the array index A[0] and the return operation), but I cannot understand why in the case where n is not 1 we have T(n-1) + 7. Why + 7? From where did we get this constant?

Also, I cannot comprehend this closed form: how did he get that T(n) = 7(n - 1) + 3?

I appreciate any help.

Answer 1

The seven operations in the case where n != 1 are:

1. The if n = 1 check
2. The calculation of n - 1 for the recursive call
3. The recursive call
4. The calculation of n - 1 for the use as a subscript
5. The A[n - 1] array access
6. The max calculation
7. The return

The final form of T(n) = 7(n - 1) + 3 comes because each of the n-1 recursive calls needs those 7 operations, while the last non-recursive call has 3.