How does time/space complexity work with lisp

Question

I'm completely new to programming but I've had a course in computational complexity. I'm trying to read the book "Structure and Interpretation of Computer Programs." In the first few sections, the authors make some claims about the relative efficiency of tree recursive and iterative processes. I find it a little frustrating that they don't formalize exactly what that mean by the run time of a program. They do mention that the interpreter uses applicative order evaluation. The problem is that it's still not totally clear what counts as one "step" of the process. For instance if one uses applicative order to evaluate the the 5th element in the sequence of Fibonacci numbers using the tree recursive algorithm fib(n)=fib(n-2)+fib(n-1), one gets

(Fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) 1))

(+ ( + (+ (+ (fib 1) (fib 0)) 1) (+ 1 1)) (+ ( + 1 1) 1))

(+ ( + ( + ( + 1 1) 1) 2) ( + 2 1))

(+ (+ (+ 2 1) 2) 3)

(+ (+ 3 2) 3)

(+ 5 3)

8

So there are ten steps, and in general fib(n) will take 2n steps: n to get to the bottom of the tree, and n to come back up. It's claimed, however, that the run time is asymptotic to fib(n). I can sort of see intuitively why this is true; the number of times in the process that two numbers are added together is clearly about fib(n), but I was hoping there is a more exact definition of run time. Any help is appreciated.

Answer 1

You get the fib(n) running time if you only expand one invocation of fib at a time. You haven't been told the exact execution model for several reasons:

1. It is messy.
2. It's not important.
3. It could depend on the implementation.
4. You need to worry about low-level stuff such as the complexity of integer operations.

The reason it's not important is that when measuring complexity we only care about the order of growth of the number of operations. So if a certain basic operation takes 3 or 13 units of time, it makes no difference for us.