On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu
wrote:
With RStF, worst case search time remains O(n), as is the
unsuccessful search. However, frequently searched elements
If you just do a linear search then shifting down the array in
another pass won't change the complexity. O(2N) == O(N) But you
could also just shift down the array while searching since if the
elements are less than the cacheline-size then you already have
everything in registers/first level cache.
(The write back cost from cache to memory is contextual and
depends on many factors.)
