1
$\begingroup$

Sources:

It can be seen that a Hash Table has no access/indexing complexity given the above sources. This doesn't make sense to me, since given a key, I can look it up in constant time by hashing it and iterating through the associated bucket (assuming the key space is less than the number of buckets, and on average). If this isn't the definition of an access/index, then how come a Binary Search Tree for example has $O(\log n)$ for access/indexing? It also doesn't do direct memory addressing and must also find the key outside that.

Also how can a Hash Table have $O(1)$ search complexity? If I'm looking to search for something, given that a Hash Table is unordered, I will on average have to search through $n/2$ nodes, giving $O(n)$ complexity. If this isn't the definition of search, then how come an array for example has $O(1)$ for access/indexing and $O(n)$ for search?

$\endgroup$

1 Answer 1

2
$\begingroup$

I think you have interchanged the idea of index and search.

Access/index here means given a position or index, like in an ordinary array or list, return the element in that index. This is why arrays support this operation in $O(1)$ time. Index or access is supported by BST because you can use them to implement sorted list. See order statistic tree for reference on how to do this. Hash table does not support index/access since the idea behind them is to "systematically scatter" elements in the structure to prevent/reduce collision, and with that, we do not expect to use such structures to maintain order of elements to support position based access.

Search on the other hand, means given an element, find it in the structure. So the $O(1)$ average search time for hashtables come from the way it searches - compute the hash of the element and perform some extra search in the bucket or probing. For arrays, with no assumptions about the elements, the only possible search is via linear search, thus the $O(n)$ running-time.

$\endgroup$
2
  • $\begingroup$ Thanks I think I get it. For example given a list [3, 7, 9, 15]. Indexing would be "return the element at position 3". And searching would be "retrieve 9". Is that correct? And would indexing in a BST only make sense if it was ordered, because there would be no concept of a position if it was unordered? $\endgroup$
    – user4779
    Apr 20, 2022 at 13:37
  • 2
    $\begingroup$ Your idea for both operations are correct. And yes, indexing in a BST works for sorted/ordered lists $\endgroup$
    – Russel
    Apr 20, 2022 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.