5 ms·

I may be missing some subtlety but it seems like this is computationally O(N) on insertion, since the eviction will have to visit and mark every node in the pat

by 3np 3y ago

I may be missing some subtlety but it seems like this is computationally O(N) on insertion, since the eviction will have to visit and mark every node in the pathological case where all existing entries are already visited? Compared to typical LRU O(logN) or O(1).

munch117 3y ago
O(N), but amortized O(1).
- 3np 3y ago
  How is it amortized O(1)? Able to prove it or at least construct an outline of an argument as to why?
  - munch117 3y ago
    Because every object stepped over is downgraded from visited to not visited. At most 1 object is set to visible per lookup.
0xFEE1DEAD 3y ago
I think you're correct about the worst case being O(n) but it's behavior heavily depends on the access pattern of the cached items which makes it hard to reason about.