CSC151 2007S, Class 20: Analyzing Procedures

Admin:
* I anticipate returning exam 1 on Monday, 
  so you need not do any readings over the weekend.
* However, a new homework will soon by available.
* And you should definitely go see Kumail Nanjiani on Saturday night.
* Today's lab is brand new

Overview:
* Overview.
* Steps.
* Lab.

An issue:
* We care about how fast our procedures run
* Experiment!
  Add a display to the start of the procedure
  (define largest-of-list
    (lambda (lst)
      (display ('largest-of-list lst)) (newline)
      (if (null? (cdr lst))
          (car lst)
	  (max (car lst) (largest-of-list (cdr lst))))))

Analyzing reverse-1

Length	Calls to myappend
0	0
1	1
2	3
3	6
4	10
5	15
6	21
7	28
8	36
9	45
10	55

8	36
16	136 = (36*4 - 8)
32	528 = (136*4 - 16)
64	2080 = (528*4 - 32)

> (analyze (reverse-1 null) myappend)
Total: 0
()
> (analyze (reverse-1 (list 0)) myappend)
myappend: 1
Total: 1
(0)
> (analyze (reverse-1 (list 0 0)) myappend)
myappend: 3
Total: 3
(0 0)
> (analyze (reverse-1 (list 0 0 0)) myappend)
myappend: 6
Total: 6
(0 0 0)
> (analyze (reverse-1 (list 0 0 0 0)) myappend)
myappend: 10
Total: 10
(0 0 0 0)
> (analyze (reverse-1 (list 0 0 0 0 0)) myappend)
myappend: 15
Total: 15
(0 0 0 0 0)

What does Sam hope you got out of this lab:
* "I should see how slow my procedure is"
  Number of recursive calls on a list of length N is ideally about N
  Number of total calls is about C*N, where C is between 1 and 10
* Using (= (length lst) 1) is a bad way to test for a one element list