The summation procedure of section 1.3.1 of SICP produces a linear recursive process with order of N space and time complexity. The code for this procedure is:
(define (sum-integers a b)
(if (< a b)
0
(+ a (sum-integers (+ a 1) b))))
What I would like to know is, if I decided that I want to sum a range of Fibonacci numbers using the analogous procedure:
(define (sum-fib a b)
(if (< a b)
0
(+ (fib a) (sum-fib (+ a 1) b))))
with fib defined as:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
How would I analyse the space and time complexity of sum-fib? Would I ignore the linear recursive flavor of the overall procedure and prioritize the tree recursion of fib within it as a worst case scenario? Would I have to somehow combine the space/time complexities of fib and sum-fib, and if so, how? Also, say I got sum-fib from another programmer and I was using it as a component in a larger system. If my program slowed down because of how fib was implemented, how would I know?
This is my first question on this platform so please also advise on how to better post and find answers to questions. Your contribution is appreciated.
There is a slight error in your code. After checking SICP, I am assuming you meant to use a > instead of a < in both sum-integers and sum-fib. That is the only modification I made, please correct me if it was done erroneously.
Note: I do not have a formal background, but this question has been unanswered for quite a while, so I thought I would share my thoughts for anyone else who happens across it.
When dealing with the time complexity, we care about how many iterations are performed as n grows larger. Here, we can assume n to be the distance between a and b (inclusive) in sum-fib. The function sum-fib itself will only recurse n times in this case. If a was 0 and b was 9, then the function will run 10 times. This is completely linear, or O(n), but it isn't so simple: the next question to ask is what happens for each of these iterations?
We know that the summation part is linear, so all that's left is the Fibonnaci function. Inside, you see that it either immediately terminates ( O(1) ), or branches off into two recursive calls to itself. Big-O notation is concerned with the worst-case, meaning the branch. We'll have 1 call turn to 2, which turns to 4, which turns to 8, etc, n times. This behavior is O(2^n).
Don't forget that this is called n times as part of the overarching O(n) summation loop, so the total function will be O(n(2^n)).
The space requirements of a function are a bit different. By writing out what's going on by hand, you can start to see the shape of the function form. This is what is shown early on in SICP, where a "pyramid" function is compared to a linear one.
One thing to keep in mind is that Scheme is tail-call optimized. This means that, if a recursive call is at the end of a function (meaning that there are no instructions which take place after the recursive call), then the frame can be reused, and no extra space is required. For example:
(define (loop n)
(if (> n 2)
0
(loop (+ n 1))))
Drawing out (loop 0) would be:
(loop 0)
(loop 1)
(loop 2)
0
You can see that the space required is linear. Compare this to:
(define (loop n)
(if (> n 2)
0
(+ n (loop (+ n 1)))))
With (loop 0):
(loop 0)
(1 + (loop 1))
(1 + (2 + (loop 2)))
(1 + (2 + 0))
(1 + 2)
3
You can see that the space required grows as the number of iterations required grows in this case.
In your case, the space required is going to increase dramatically as n increases, since fib generates a full tree for each number, and is not tail-recursive, nor is sum-fib.
I suspect that the space required will also be O(n(2^n)). The sum-fib function (ignoring the fib calls), seems to be linear in space, or O(n). It calls 2 fibs per iteration. Each fib branches off into 2 more, and is not tail-recursive, so the space required is O(2^n). Combining them, we get O(n(2^n)). Whether or not this will always be the case, I am not certain.
What you are looking for is called a profiler. It will watch your code while it runs, and report back to you with information on which functions took the most time, which functions were called most often, etc. For Scheme, Dr. Racket is an IDE which has a built-in profiler.
A word of advice: Get your software working first, then worry about profiling and optimizations. Many programmers get stuck in hyper-optimizing their code without first finishing to see where the true bottlenecks lie. You can spend weeks gaining a 1% performance boost utilizing arcane algorithms when it turns out that a 5-minute tweak could net you a 50% boost.