3 ms·
> what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Problem ill-stated as posed: Does not specify if the '
by derleth 13y ago
> what is a time complexity for finding a next item (according to a key) to a given one in a hash table?
Problem ill-stated as posed: Does not specify if the 'next' key is hashed, or even what 'next' means in this context.
- mixedbit 13y agoSay, the smallest item in a hash table for which item.key is larger than given_item.key. Assume larger-than relation for keys is defined, so for example keys are integeters.
- sillysaurus 13y agoSay, the smallest item in a hash table for which item.key is larger than given_item.key. Well, keys in a hash table are hashed. This implies that unless you're searching for a specific key (e.g. "42") rather than a condition (e.g. "smallest key greater than 42") then the time complexity is necessarily O(N).
- mixedbit 13y agoCorrect :)