Re:The true cost of linked lists
by pjungwir on Monday June 06, 2022 @03:21PM
(#31644763)
It looks like you intended your first snippet to end with `return result` not `return i`, right?
Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)
Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)