This is the paper the article is about: arxiv.org/pdf/2501.02305
BeigeAgenda@lemmy.ca 2 weeks ago
Here’s a link to the paper “Tiny Pointers” arxiv.org/pdf/2111.12800 those editors at Quantamagazine writes their summary in a strange fashion, for instance using x in stead of n which is normally used in computer science when talking about big O notation.
Lojcs@lemm.ee 2 weeks ago
deegeese@sopuli.xyz 2 weeks ago
In the article, x is not the size of the hash table, it is the inverse of the table’s filling fraction. A 1000-element table that is 90% full has x=10, N=1000.
Since they’re not discussing scaling of data sizes, would be confusing to use O(N) notation or people would make that assumption.