Я бы предположил, что assoc - это O (n) *, предполагая, что equal? - это O (1) в вашем использовании функции. Это потому, что написать свою версию assoc:
тривиально
(define (my-assoc v lst)
(cond ((null? lst) #f)
((equal? v (caar lst)) (car lst))
(else (my-assoc v (cdr lst)))))
Вы можете видеть, что это просто скользит вниз по списку lst, пока не будет найдено совпадение. Если ничего не найдено, возвращается #f.
* технически equal? - это O (n), где n - размер меньшего ввода, поэтому, если вы сравниваете огромные структуры списка, используя assoc, время выполнения будет O (n * m), где n - размер списка, предоставленного assoc, а m - размер v.