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?


closed as unclear what you're asking by D.W., Rick Decker, David Richerby, Juho, R B Dec 22 '14 at 17:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.


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