How can I concatenate two sequences of lists (either lists of lists or vectors of lists) in constant time (independent of their size)?
I'm not sure you can avoid some size dependent time cost as you'll need to iterate over one list or the other to join them together. If you know your new list is shorter than the list you are adding to then you can just
push them to the front:
(let ((l '(4 5 6 7)) (n '(2 3))) (cl-map 'nil (lambda (x) (push x l)) n) l) ==> (3 2 4 5 6 7)
That said I tend to favour the dash functions and just -concat:
(let ((l '(4 5 6 7)) (n '(2 3))) (-concat n l)))
which according to disassemble ends up with almost the same byte code but probably because it can optimise the simple example.