What is the time complexity of 'assoc' function in scheme?

Question

What is the time complexity of this nifty function 'assoc'?

Answer 1

I would assume that assoc is O(n)*, assuming that equal? is O(1) in your usage of the function. This is because it's trivial to write your own version of assoc:

(define (my-assoc v lst)
  (cond ((null? lst) #f)
        ((equal? v (caar lst)) (car lst))
        (else (my-assoc v (cdr lst)))))

You can see this simply slides down the list lst until a match is found. If none is found, #f is returned.

* technically equal? is O(n) where n is the size of the smaller input, so if you're comparing huge list structures using assoc, your runtime will be O(n*m) where n is the size of the list provided to assoc and m is the size of v.