patternMinor
Why is Big O not defined here for a hash table?
Viewed 0 times
whyheretablehashbigfornotdefined
Problem
In this cheat sheet, average time complexity for access to a hash table is listed as N/A.
I'm curious as to why. Since a hash table is mostly mathematical, I would assume it would be O(1) like the other operations ... Search, Insertion, Delete.
http://bigocheatsheet.com/
I'm curious as to why. Since a hash table is mostly mathematical, I would assume it would be O(1) like the other operations ... Search, Insertion, Delete.
http://bigocheatsheet.com/
Solution
The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹.
In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a.
In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a.
- Which is of course underspecified or unfair, depending on how you look at it: in a BST, "Access" gives you also the $i$-th smallest element, whereas in a plain array you get just some element.
Context
StackExchange Computer Science Q#82669, answer score: 6
Revisions (0)
No revisions yet.