1. Note on tail-recursion and running time:
   There are two resources that we usually want to measure: the running time of
   the program, and the space it takes.
   The running time of a function _is not_ affected by the fact that it is tail
   recursive or not - this is just a matter of space needed for its running.
   For example, the two times function versions (times-1 and times-2) that you
   some time ago in class have the _same_ running time, just different space
   needs.  The fact that there is less to save on a "stack" can, of course,
   make things run faster, but this is not really our problem.

2. We saw the calculation of the "times" function running time:
   [note on cond, if they don't know it yet]
     (define (times <function>)
       (method ((a <number>) (b <integer>))
         (cond (((= b 0) 0)
                (else: (+ a (times a (dec b))))))))
     T(0) = c
     T(b) = T(b-1) + c
          = T(b-2) + 2c
          ...
          = bc
     => "times" has a running time of O(b)
   "fast-times" had a better run-time:
     (define (double <function>) (method ((n <integer>)) (* n 2)))
     (define (halve <function>) (method ((n <integer>)) (/ n 2)))
     (define (fast-times <function>)
       (method ((a <number>) (b <integer>))
         (cond ((= b 0)   0)
               ((even? b) (fast-times (double a) (halve b)))
               (else:     (+ a (fast-times a (- b 1)))))))
     T(0) = c
     T(b) = T(b/2) + c if b is even > 0
     T(b) = T(b-1) + c if b is odd
   In the lecture, we the easy case, where b is a power of 2.
     b = 2 ^ (log_2 b)
     => T(b) = T(b/2) + c
             = T(b/4) + c + c
             = T(b/8) + c + c + c
             ...
             = T(1) + (log_2 b) * c
             = T(0) + (1 + log_2 b) * c
             = (2+log_2 b) * c
             = O(log b)

   Big-O is worst case analysis:
   We see that best case is O(log b), if every call to fast-time results in the
   even case.  But we really should consider the worst-case - what if b is not
   a power of two?  In fact, what if b was chosen so that every other call to
   fast-times resulted in the odd case (try 255)?  Here we have the worst case
   scenario.  b starts out as odd, and every division by two results in an odd
   number.
     T(b) = T(b-1) + c                    <b is odd>
          = T((b-1)/2)) + c + c           <(b-1) is even>
          = T(((b-1)/2)-1) + c + c + c   <odd>
          = T((((b-1)/2-1)/2) + c + c + c + c
          ...
          = T(1) + log_2(b) * c + log_2(b)*c
          = T(0) + c + 2*log_2(b) * c
          = O(log b)
   So, in the worst case, T(b) costs twice as the best case, because at least
   every other call is to even number - so we still have an overall complexity
   of O(log n).

3. That trick for fast programs can be applied in many places, even in the
   "repeated" function - replace this:
     (define repeated
       (method (f n)
         (if (zero? n)
           identity
           (method (x) ((repeated f (- n 1)) (f n))))))
   by:
     (define fast-repeated
       (method (f n)
         (cond ((zero? n) identity)
               ((even? n) (fast-repeated (double f) (halve n)))
               (else: (method (x) ((fast-repeated f (- n 1)) (f n)))))))
   only now "double" operates on functions (try guessing its value):
     (define double
       (method (f)
         (method (x) (f (f x)))))

4. A quick review + explanations on the meaning of complexity:
   First of all, remember that the complexity is an estimation of the order of
   growth - you shouldn't bother yourself with minore things as constants...
   There is a big difference between a program running double the time of a
   different program, but this does not change the running time too much (wait
   two years and you'll have 10x faster computers...)
   Complexity is the "order of growth" - an indication of the _change_ in
   resources implied by changes in the problem size.
   O(1) - Constant growth: resource requirements do not change with the size of
          the problem.
   O(log n) - Logarithmic growth: _multiplying_ the problem size implies a
              _constant increase_ in the resources.
              For example: if Time(n) = log(n),
                         then Time(2n) = log(2n) = Time(n) + log(2),
                          and Time(6n) = log(6n) = Time(2n) + log(3), etc.
   O(n) - Linear growth: Multiplying the problem size _multiplies_ the
          resources by the same factor.
          For example: if Time(n) = Cn
                     then Time(2n) = 2Cn = 2Time(n),
                      and Time(4n) = 4Cn = 2Time(2n), etc.
          Hence, the resource requirements grow _linearly_ with the problem
          size.
   O(n^c) - Polynomial growth: Multiplying the problem size _multiplies_ the
            resources by _a power_ of that factor.
            For example: if Time(n) = n^c,
                       then Time(2n) = (2n)^c = Time(n)*(2^c),
                        and Time(4n) = (4n)**a = Time(2n)*(2**a), etc.
            Linear growth is a specific case where c=1.
   O(C^n) - Exponential growth: Any _constant increment_ in the problem size,
            _multiplies_ the resources by a constant number.
            For example: if Time(n) = C^n,
                       then Time(n+1) = C^(n+1) = Time(n)*C,
                        and Time(n+2) = C^(n+2) = Time(n+1)*C, etc.
   These explanations are the intuition behind the patterns we saw in class:
     Pattern 1
       T(n) = T(n-k) + c
       T(0) = c
       is O(n), where k, c are constants
     Pattern 2
       T(n) = T(n/k) + c
       T(0) = c
       is O(log n)
   Of course, we have:
     O(1) < O(log n) < O(n) < O(n*log n) < O(n^c) < O(2^n)
   Programs with exponential run-time and more are considered a nightmare.

5. Note: Structure for test question:
   - Design a data structure to do x,
   - Implement these operations to do x,
   - Do a running time analysis on the code you wrote.