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
- abseil / Performance Hintsabseil.io
- lecture14.pdfweb.stanford.edu
- Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowellbigocheatsheet.com
- abseil / Performance Hintsabseil.io
- Hash Tablesalgs4.cs.princeton.edu
- Accidentally Quadraticaccidentallyquadratic.tumblr.com
- Competitive Programmer's Handbookcses.fi
- Build Your Own Databasenan.fyi
- Big Osamwho.dev
- Memory access is O(N^[1/3])vitalik.eth.limo
- Big O Cheat Sheet – Time Complexity Chartfreecodecamp.org
- Hash function - Wikipediaen.wikipedia.org