In order to measure how fast programs runs, we have to devise a reasonable way to do so. Using a stopwatch to measure how much time it takes wouldn't work because the timings would change each time we had different programs running in the background, random fluctuations, solar flares, etc. Moreover, new computers are generally faster and old timings wouldn't be applicable.
A better way to approach this is to count the number of steps that a procedure takes. Focusing on the procedure allows us to avoid the problem of being tied down to any particular computer.
Here are some of the procedures we'll consider as taking "one step":
All of the following procedures take a single step.
(define (square x) (* x x)) ; takes a single step (square 4) ; would take 2 steps (one for the procedure call, and one for the multiplication) (square (+ 2 3)) ; 3 steps
However, the most interesting questions arise when we compare one procedure to another, and ask which one is faster. In order to make this comparision, we must ask the following for each procedure:
As we increase the size of the argument, how many steps will this procedure take to run?
In other words, if we were to graph the number of steps a procedure takes (with the input as the x-axis), what is the shape of that graph?
square, we say this is a constant time procedure--
(square 2)takes as many steps as
(square 2000). So as we increase the size of our input, the number of steps remains constant.
last, the procedure that finds you the last word of a sentence, we say this is a linear time procedure--as we call
laston larger and larger inputs, the number of steps grows linearly.
In order to formalize this, we have to learn a mathematical construct called Orders of Growth.
Orders of Growth describe the relationship between functions. Given two functions f(n) and g(n), when we say f = Θ(g), we mean that there exists two numbers, a, and b such that ag(n) ≤ f(n) ≤ bg(n) for sufficiently large values of n.
Based on these examples, we have the following rules
Coming back to procedures, we can formally say that
square is Θ(1), and
last is Θ(n).
Consider the straightforward way to compute
b to the
nth power): multiply
b against itself
n times. Here's the code for that.
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))
This runs in linear time with respect to the
n variable. We know this because of two observations
nis 2, we make two recursive calls and if
nis 10, then we make 10 recursive calls.
Can we do better? Turns out there's a more clever exponentiation algorithm that takes advantage of the follow idea of successive squaring.
Let's say we were trying to compute b^8. Normally, we would do b * b * b * b * b * b * b * b. This requires 8 multiplcations. Instead we can do it in 3: This method works fine for exponents that are powers of 2. We can also take advantage of successive squaring in computing exponentials in general if we use the rule
The above tricks give us this procedure:
(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1)))))) (define (even? n) (= (remainder n 2) 0))
Squaring every even number allows us to cut down on the number of recursive calls. In fact, if you think about it, every other recursive call, we cut down
n by half. This pattern of reducing the problem by half is means that the number of recursive calls taken is logarithmic with respect to
fast-expt = Θ(log(n)). (If this explanation doesn't make sense, check out 1.2.4. in the Further Reading)
Here are short, ungraded exercises for practice with finding the runtime of a function.
define (bar n) (if (zero? (remainder n 7)) 'Bzzst (bar (- n 1)) ))
(define (sort s) (if (empty? s) '() (insert (sort (bf s)) (first s)) )) (define (insert sorted-sofar n) (if (empty? sorted-sofar) (se n) (if (< n (first sorted-sofar)) (se n sorted-sofar) (se (first sorted-sofar) (insert (bf sorted-sofar) n)) )))