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.