Isn't it, then, better not to specify the order so that implementation
may choose how it's implemented at least for this particular procedure?
Or do the orders indicate worst cases?
I have the same question/comment. Technically, by the definition of O ( http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf ), O(1) is a subset of O(n), so if a procedure takes O(1) time it is sound to also say that it takes O(n) time. So an implementation with an O(1) queue-length would comply with the SRFI, but I get the sense that's not what's intended. ϴ (theta) notation can be used to indicate that a procedure be linear and no faster, i.e. ϴ(n).