I don't understand how these two variables are proportionate

Question

Structure and Interpretation of Computer Programs section 1.2.1 Linear Recursion and Iteration:

Compare the two processes... each requires a number of steps proportional to n to compute n!

The two processes are specified by

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

;; This is the linear recursive process

(define (factorial n)
 (define (iter product counter)
   (if (> counter n)
       product
       (iter (* counter product)
             (+ counter 1))))
 (iter 1 1))

;; This is the linear iterative process

My question is: how do both processes require a number of steps proportional to n to compute n! ?

Answer 1

For the 1st process; you have to do these steps in one recursive loop:

- check if n equals 1
- multiply n with (factorial (- n 1))
  if we split it a little, it includes (- n 1) and a function call and a multiplication.

Let just roughly count these as 4 steps.

And because you have to do these 4 steps until n = 1, totally it is 4*n steps. so it is proportional to n. (let's ignore some details, e.g., processing of n=1 case is a little bit different because when n is large enough, it can be ignored)

The 2nd one is the same