Let $x \in \{ \log n, n, \dots , n!\}$ some (cost) function.

Are there interesting operations with runtime in $O(x)$ on lists which also have runtime in $O(x)$ on hash tables?

  • $\begingroup$ Sure, given two arrays of same size n, we can find the union and the intersection in O(2*n) or O(n) time and this is also the same complexity for a hash table $\endgroup$ – Olórin Dec 17 '14 at 8:52
  • 1
    $\begingroup$ Please be more precise about what model of computation and what notion of running time you have mind. When you speak about hash table running time, are you talking about expected running time? worst-case running time? Can we assume you've used a 2-universal hash function? etc.? Lookup takes $O(n)$ time in a list and $O(n)$ worst-case time in a hash table; why is that not an answer to your question? Please edit your question to tell us what you tried and be more precise about your requirements, so that it's clear what would count as a valid answer. $\endgroup$ – D.W. Dec 19 '14 at 1:35

Lookup (testing whether the list/table contains a particular element $v$) takes $O(n)$ time in a list and $O(n)$ time in a hash table, in the worst case. So, the worst-case running time is the same for both data structures.

| cite | improve this answer | |

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