Space and time for a few procedures.. (Scheme procedures, that is)

Hey everyone,
I apparently had an account here but forgot..? Any way, I wasn't able to make it to class last time and as a result, missed out on some good 'big O' discussion as well.

I have a scheme midterm next week and I'm hoping someone here can help me understand the concept of time and space, and then maybe break down the procedues and show me what/why the time and space of each is.

I'll start with 2-3 procedures today:

(define (accumulate proc init alist)
(cond ((null? alist) init)
(else proc (car alist) (accumulate proc init (cdr alist))))))

(define (insert x alist)
(cond ((null? alist) (cons x alist))
((> x (car alist))
(cons (car alist) (insert x (cdr alist))))
(else
(cons x alist))))

(define (enumerate start end)
(cond ((> start end) ())
(else
(cons start (enumerate (+ start 1) end)))))


(define (filter test alist)
(cond ((null? alist) ())
((test (car alist))
(cons (car alist)
(filter test (cdr alist))))
(else
(filter test (cdr alist)))))


Okay, so that's 4. Sorry I need to know space and time... and I'll be honest, I haven't tested them in Dr. Scheme yet. I'm trying to figure out what the procedues are even (insert looks easy enough). I need to know how to test them as well. ANY help will be appreciated.. so err, please do so

ok, c'mon, a few of you might know Scheme.... well at least 3% or so says the poll

I can give you a quick-and-dirty informal analysis, but you'll need to do any formal work yourself. OK, let's start with this one:



Since this is a functional, the actual time and space will depend on the function being applied, but the (accumulate) function itself is a simple linear time - O(n) - operation: it makes exactly one pass over each of the items in alist. Since the function is not tail recursive (it accumulates the results from the later values first, then performs the final operation afterwards), the function is called for each pass, so it is also linear in space.

Now for (insert):



Here, the function tests each element of a sorted list: if the value of x is greater than the current element (the (car) of alist), then it recurses on the remainder of the list and conses the result to the current element. If it finds an element greater than or equal to x, then it returns the remainder of alist consed to x. If it reaches the end of the list without finding a larger value, it simply returns x. Walking through an example (insert 4 '(1 3 3 4 7)), you would get


As you can see, the algorithm would pass through each element at most once, so again, the upper bound of the time is linear; in the worst case (i.e., x is higher than any current element of alist) will take one pass per list element, plus one for the null element at the end of the list. Since the algorithm is non-tail recursive, and there is one recursive call per element, the space is also linear worst case (actually, it is marginally less than linear, since the list decreases with each pass, but that's not really consequential).

This should give you some idea of how to at least estimate the efficiency of relatively simple functions like these. Keep in mind that the values for big-O notation are relative efficency; they don't measure the absolute speed of the function (which would depend on the particular implementation), but rather, how the efficency scales with size of the arguments.

References:
Wikipedia: Big O Notation
NIST article: Big O Notation
Complexity and Big O Notation
Big-O Notation and Algorithm Analysis