pjstirling wrote: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.