Hacker News new | comments | show | ask | jobs | submit login

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).

Correct :)

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact