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.