Solution to Analysis of Algorithms

WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.

1. pairs(n) = pairs(n-1) + (n-1)
            = pairs(n-2) + (n-2) + (n-1)
       ...  = pairs(1) + 1 + 2 + ... + (n-2) + (n-1)
   pairs(1) = 0, pairs(n) = (n(n-1))/2

2. The process generated by the all-pairs procedure is recursive. Each call to all-pairs generates a pending operation, which means that it uses more space the longer it runs. You can tell that it is recursive rather than iterative because after each recursive call to all-pairs, the function must still perform the append operation. If it were iterative, then a 'marker' parameter would be necessary to keep track of the iteration.

3. for (l <list>) of length n 
       - pair-with-list is O(n)
       - length (pair-with-list x l) => n where x is any object
   T(n) = T(n-1) + O(n-1) + O(n-1) + C
          ^all-pairs ^append  ^pair-with-list
           recursive call      (length (tail l)) => n-1
        = T(n-2) + 2O(n-2) + 2O(n-1) + C
    ... = T(1) + 2O(1) + 2O(2) + ... + 2O(n-1) + C          T(1) = C
        = 2O((n(n-1))/2) = O(n2)

Question

Return to CS 212 Prelim 1 - Spring 1997