13.3 ISBN Cache

**fondant** · February 18, 2018, 10:54pm

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?

**tsunghsienlee** · February 21, 2018, 5:20am

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.