CS212 Exams
Spring 1998 - Prelim 1

Analysis of Algorithms

You are to analyze the running time for a function tail-sums (defined below). The function takes a list of numbers, say n1, n2, ... , nm and returns a list of numbers s1, s2, ... , sm where $s_i = \sum_{j=i}^{m} n_j$.

   (define (sum-list x)
     (if (empty? x) 0 (+ (head x) (sum-list (tail x)))))

   (define (tail-sums y)
     (if (empty? x) empty (cons (+ (head x) (sum-list (tail x)))
                                (tail-sums (tail x)))))

For example: (tail-sums '(1 2 3 4 5)) evaluates to the list '(15 14 12 9 5).

 

a.
tail-sums is defined in terms of sum-list. What is the running time (using big-O notation) of sum-list in terms of n, the length of the input list x? (You need not justify your answer.)




b.
Write out a set of recurrence equations that summarizes the time to run tail-sums in terms of the length m of the input list y. Be sure to give equations for T(0) (the time to run tail-sums on an empty list) and for T(m+1). The latter should be expressed in terms of T(m) and the time to run sum-list on a list of length m.




c.
Determine a closed form solution (i.e., a single definition for T(m) without any recurrence) for the running time of tail-sums. Use big-O notation to express the result.




d.
Write a new function, tail-sums-2, which is asymptotically more efficient than tail-sums.




Solution

Return to CS 212 Prelim 1 - Spring 1998