13.3 ISBN Cache

#1

I don’t understand what this line means:
"The drawback of this approach is the O(n) time needed for some lookups that miss on a full cache"
in the context of inserting 2n entries into the cache before deleting half of them. Why would a lookup take O(n) time?

0 Likes

#2

Hi @fondant,

There is a typo there as it shall be insert instead lookup. Because insertion might cause new entry which might trigger the O(n) additional time here.

0 Likes