Re:Big-O Algorithm Complexity Cheat Sheet
by mixedbit on Saturday May 04, 2013 @02:05PM
(#5655704)
Say, 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.
[ Parent
| on HN ]
Re:Big-O Algorithm Complexity Cheat Sheet
by sillysaurus on Saturday May 04, 2013 @02:11PM
(#5655731)
Say, 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).