Analysis of Algorithms

Microsquishy has decided to re-implement their Exmell Spreadsheet using DrSwindle. You have been hired by Gill Bates to demonstrate to the US Government that Microsquishy programmers are incompetent and so the Government should cut them a break in their current anti-trust suit. Your analysis for the court will help show that the functions would be coded much better if only the Microsquishy programmers had attended Cornell. Here is their code:

; Extracts the nth element of a list x
; (first element is at position 0.)
; Assume the list is non-empty.
(define (nth-elt x n)
  (if (= n 0)
      (head x)
      (nth-elt (tail x) (- n 1))))

; Calculates the length of a list.
(define (length x)
  (if (empty? x)
      0
      (+ 1 (length (tail x)))))

; Reverses a list x.
(define (reverse x)
  (let ((len (length x)))
    ; rev-x contains elements [n-1,n-2,...,3,2,1,0]
    (define (iter n rev-x)
      (if (= n len)
          rev-x
          (iter (+ n 1) (cons (nth-elt x n) rev-x))))
    (iter 0 empty)))

The users of Exmell report that it takes a really long time to reverse a list.  So, you decide to show the court that the asymptotic performance of reverse is actually quite bad. To simplify your analysis, you break the report to the Government into pieces.

1. What is the running time (using big-O notation) for nth-elt when given a list x (whose length is i) and the integer value n? You should express the time as a function of i and n.
   
   
2. The function reverse calculates the length of the list and then calls iter. What is the running time (using big-O notation) for the call to length on a list whose length is i?
   
   
3. The function iter has two arguments: an integer n and a list rev-x. Notice that at every call to iter, rev-x has length n. Express the running time of iter in terms of n as a set of recurrence equations - one equation for n = 0, and one equation for n = m + 1 (in terms of m).
   
   
4. Solve the recurrence equations generated in the previous part to calculate a closed-form solution for the running time of iter and use this to determine the total running time for the Microsquishy implementation of reverse.
   
   

Solution

Return to CS 212 Prelim 1 - Spring 1999