CS212 Exams
Fall 1996 - Prelim 1

Analysis of Algorithms

This problem is concerned with the order of growth of functions. Consider the following code for reversing a list 
(define (reverse l)
    (if (empty? l)
        l
        (append (reverse (tail l)) (list (head l)))))
  1. Write a recurrence describing the running time of reverse as a function of the length of the list l. Just write the recurrence, don't try to solve it for a closed form (non-recursive definition). Remember to consider both the general case of T(n) and the case of T(0).




  2. What is the running time of reverse in ``Big-Oh'' notation, as a function of n, the length of the list l? Briefly justify your answer, you may use the recurrence from above or some other concise argument.




  3. What is the fastest possible running time, in ``Big-Oh'' notation, for a Scheme procedure that reverses a list? Briefly justify your answer.




Solution

Return to CS 212 Prelim 1 - Fall 1996