Re:When Big O Fools You
by thaumasiotes on Tuesday August 23, 2016 @06:00PM
(#12348105)
> But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.
This is true if you already have a reference to the middle of the list. If you don't (say, because you want to insert while preserving the fact that the list is sorted), then inserting into a linked list is O(n) just like the array is.
Memory reads and memory writes are not the same. Linked list insert in the middle needs to do only O(1) writes. But because linked lists preclude memory prefetch, they should not be used these days.
Re:When Big O Fools You
by fixerfrasse on Tuesday August 23, 2016 @04:52PM
(#12347517)
Afaik, if you read in reverse, then you will miss cache optimization since it only works forward.
Intel cache prediction will detect both forward, backward, and some odd movement patterns. It has not been only forward prediction for a very long time.
Do you know how the popular ARM based chips fare in comparison?
But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.
The OP is discussing inserts at the start just because it is the worst-case scenario for arrays, then a positive result will still be true if some of the inserts are in the midddle or even near the end.