6 ms·
> Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the t
by pcthrowaway 4y ago
> Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers
This is a great point. If you're sorting an array of strings, you would never add an extra m in that complexity analysis for the size of the longest string, in bits (not length, because unicode)
The OP seems wrong to make candidates do this
- jameshart 4y agoAnother thing we ignore in big-O analyses: as a hashtable grows arbitrarily large, the physical media in which it’s data is stored must also take up more and more physical space. Since we live in three-dimensional space, the retrieval time for a hashtable containing n entries must be bounded by the fact that the entries are located a distance of at least O(n^1/3) away. (Not actually purely an academic concern - this physical constraint is what drives the difference in performance between using data in L1cache, RAM, disk, or on remote networked nodes.) So yeah, O(1) hashmap reads are a convenient lie we tell ourselves, which are really only true for ‘small hashmaps’.