How to properly calculate the order of growth of an exponential algorithm? I'm reading SICP, and I'm a little bit confuse about this statement:


  Consider the problem of computing the exponential of a given number.
  We would like a procedure that takes as arguments a base b and a
  positive integer exponent n and computes b n . One way to do this is
  via the recursive definition

b n = b ⋅ b n − 1 ,
b 0 = 1

  
  which translates readily into the procedure

(define (expt b n)
  (if (= n 0) 
      1 
      (* b (expt b (- n 1)))))

  
  This is a linear recursive process, which requires Θ ( n ) steps and Θ
  ( n ) space.


I did a tree illustrating the process generated by the procedure:

(expt 2 2)
|
|
|
(expt 2 1)


Which makes the statement "This is a linear recursive process, which requires Θ ( n ) steps and Θ ( n ) space." true. But when I use a substitution model, it seems that requires 0 ( n ^ 2) steps and space:

(expt 2 2)
    (* 2 (expt 2 1))
    (* 2 2)
4


Thank you.
In this answer we assume the arithmetic model of computation, in which each arithmetic operation has cost 1.

The question has bad notation. Define function expt b n to compute b^n as:

expt b 0 = 1
expt b n = b ⋅ expt b (n − 1)


Computing expt b n requires computing n-1, computing expt b (n-1), and multiplying that expression by b. So the cost of expt b n is $2 +$ the cost of expt b (n-1). expt b 0 has cost 0.

Putting the above together, we see the cost of exp b n is $2 +$ the cost of exp b (n-1), $= 4 +$ the cost of exp b (n-2), $\ldots$, $= 2n +$ the cost of exp b 0, $= 2n$.