In general, hash map lookups are considered O(1) in the size of the hash map. Which is not the n the author is using, to begin with.
But.
Hashmap lookups require calculation of a hash of the key. Calculating the hash of a key requires examining all of the bits in the key. If the keys are int32s, then the hash algorithm has to read 32 bits. If they're int64s, then the hash algorithm has to read 64 bits.
And if your hash map contains n distinct values, then at a minimum they must be drawn from a key space where each key contains O(log n) bits. If you want a hash map to contain more than a few billion values, you'll need bigger-than int32-sized keys to distinguish them, right?
So for any hashmap of size n, that means there's an O(log n) hash calculation in there. (especially when we are considering the asymptotic case where the hash map grows infinitely large... such hash maps will necessarily have infinitely long keys, too)
Yet we call hash map lookups O(1).
Because in practice we imagine a hash map has a key space of a fixed size (even though such a constraint would mean that the hash map has a fixed maximum size and therefore no asymptotic performance case since it can't scale to infinity).
By playing around with big-O on hash table lookups with keys of size n, the interviewer is skating dangerously close to this contradiction at the heart of big-O analysis of hashmaps...
But unnecessarily so, since the key space they're using is dictionary words, which have a maximum length, so their length isn't the n you're looking for.
(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. Is it a hand wave? Probably not when you're dealing with numbers. Maybe when you're dealing with strings)
> 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)
Another 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’.
But.
Hashmap lookups require calculation of a hash of the key. Calculating the hash of a key requires examining all of the bits in the key. If the keys are int32s, then the hash algorithm has to read 32 bits. If they're int64s, then the hash algorithm has to read 64 bits.
And if your hash map contains n distinct values, then at a minimum they must be drawn from a key space where each key contains O(log n) bits. If you want a hash map to contain more than a few billion values, you'll need bigger-than int32-sized keys to distinguish them, right?
So for any hashmap of size n, that means there's an O(log n) hash calculation in there. (especially when we are considering the asymptotic case where the hash map grows infinitely large... such hash maps will necessarily have infinitely long keys, too)
Yet we call hash map lookups O(1).
Because in practice we imagine a hash map has a key space of a fixed size (even though such a constraint would mean that the hash map has a fixed maximum size and therefore no asymptotic performance case since it can't scale to infinity).
By playing around with big-O on hash table lookups with keys of size n, the interviewer is skating dangerously close to this contradiction at the heart of big-O analysis of hashmaps...
But unnecessarily so, since the key space they're using is dictionary words, which have a maximum length, so their length isn't the n you're looking for.
(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. Is it a hand wave? Probably not when you're dealing with numbers. Maybe when you're dealing with strings)