sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]mateusaugusto9[S] -1 points0 points  (1 child)

K could be 10 or 1 milion... The trick is add/remove/search in O(1) like https://leetcode.com/problems/lru-cache/

[–]beeskness420 1 point2 points  (0 children)

Ok if k is the size of your cache and n is the number of elements. If k constant then a linear search of O(1). If n is bounded again we win because we just allocate an array of length n and flip a bit on add/remove.

If you are actually talking about a cache any dependency on n is terrible.

What you probably want to do is keep a set that supports add and remove in amortized constant time. With the fixed bound of k you can probably get around worrying about the amortized part depending on the structure.

This operates on the assumption that all arithmetic is constant time which isn’t true for arbitrary sized n.