delete does not work

[sylwester]

Using a loop over POP is O(n) in both.

pop does a setq. It won't alter the argument. In my description I'm doing consecutive delete of random elements until I'm at one last using double loop will end up being O(n^2) time and O(1) space. By making the delete O(1), as in hash, you can get it O(n) time in total.

delete is not about time complexity. It's about space complexity. Using remove will cons n^2 times. eg, a small list of a million elements will cons 8TB memory on a 64 bit machine while none by using delete. If you want a functional interface you copy the initial list ie. cons 8MB. It sure beats 8TB memory usage. When you have a copy using delete in place of remove is not possible to detect by the user except perhaps the user gets the result the same day.

[David Mullen]

It says something about the appeal and tractability of Lisp's lists that we're talking about million-element lists. I mean, you could argue for a vector because that would halve the per-element overhead. But it's kind of hard to beat the sheer handiness of lists. It's why we all (most of us, anyway) reach for lists first, despite the other structures on the menu. (And, hey, they've worked out pretty well for representing source code.)

[sylwester]

Not using mutating functions is the way to go when developing since you don't want to spend time micro optimizing code that does not need optimization.
delete *is* compatible with remove in every implementation of Common Lisp so I don't understand how you can state remove is more compatible.
As long as you, in the same way as remove, use the returned value you are in the clear with both functions.