Lecture 20: Amortized Analysis
The claim that hash tables have O(1) expected performance for lookup and insert is based on the assumption that the number of elements stored in the table is comparable to the number of buckets. If a hash table has many more elements than buckets, the number of elements stored at each bucket will become large. For instance, with a constant number of buckets and O(n) elements, the lookup time is O(n) and not O(1).
Lecture 20: Amortized Analysis Lecture 20: Amortized Analysis The claim that hash tables have O (1) expected performance for lookup and insert is based on the assumption that the number of elements stored in the table is comparable to the number of buckets. If a hash table has many more elements than buckets, the number of elements stored at each bucket will become large. For instance, with a constant number of buckets and O ( n ) elements, the lookup time is O ( n ) and not O (1). The solution to this problem is to increase the size of the table when the number of elements in the table gets t
related reading
- Amdahl's law - Wikipediaen.wikipedia.org
- Memory access is O(N^[1/3])vitalik.eth.limo
- lecture14.pdfweb.stanford.edu
- Transformer Inference Arithmetic | kipply's blogkipp.ly
- Hash Tablesalgs4.cs.princeton.edu
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”youtube.com
- Static search trees: 40x faster than binary search · CuriousCodingcuriouscoding.nl
- p197-wang.pdfvldb.org
- A very concrete explanation of how a cache worksparksb.github.io
- lfu.pdfdhruvbird.com
- Introduction to Locality-Sensitive Hashingtylerneylon.com
- Time complexity of operations on built-in typesdocs.python.org