3
$\begingroup$

I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that:

"Hopefully, all the elements that are in your set happen to be placed into different entries in the table. In this case one can

  • determine whether or not an element is contained in the set,
  • ask for an arbitrary element form the set,
  • determine the number of elements in the set,
  • iterate through all the elements,
  • and add and delete elements

in constant time i.e independently of the number of items in the set."

when speaking about hash tables. I don't understand how it is possible to iterate through all the elements in constant time. Shouldn't it be $O(N)$ since we iterate through all of them?

$\endgroup$
  • 2
    $\begingroup$ The key point here is the rather unrealistic assumption "all the elements in your set happen to be placed into different entries in the table", in other words if $x\ne y$ then $x$ and $y$ will be in different buckets in the table. In that case, iterating over all the elements can indeed be done in constant time for each element, though of course as you correctly note, you can't possibly inspect $N$ elements in constant time. A poorly worded explanation, in my opinion. $\endgroup$ – Rick Decker Oct 14 '14 at 14:00
  • 1
    $\begingroup$ Yeah, it looks like either a poor explanation or just a silly error the author would blush over. Clearly you can't iterate over $n$ elements in time less than $\Omega(n)$. $\endgroup$ – Patrick87 Oct 14 '14 at 14:36
2
$\begingroup$

What you said is true. You can't iterate through all the elements in a hash table in constant time. It would take $O(N)$. But the author is not actually talking about all the elements in the hash table, but to iterate though each single element (in which there is only one element, making it constant). It comes down to the assumption here:

"all the elements that are in your set happen to be placed into different entries in the table."

In this case for each element, there is a single node. If this was not true you need to form a link-list for the hash table table, that is when there is collision. Then for each element it's no longer a constant time. But whatever item in the hash table happens to have the longest list.

Again, the explanation isn't clear here. As it looks like the author is saying iterating through all the elements in a hash table, and not iterating through for each element.

$\endgroup$
2
$\begingroup$

I don't agree that the author was talking about iterating over a set with constant time per element. I've never seen iteration described in time per element. It's certainly not common enough to be an unspoken assumption. I would guess that instead it's simply an editing miss.

$\endgroup$
0
$\begingroup$

The definitions aren't clearly given in the fragment of the book that Google showed me.

Clearly, if the table has $N$ entries and each entry contains at most one item, you can iterate through all the items in time $\Theta(N)$. Now, if $N$ is some fixed constant, $\Theta(N)$ time is constant time – and the set has constant size. On the other hand, if $N$ is some variable that depends on the length of the input, then all the bets are off.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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