1
$\begingroup$

I am designing a graph algorithm. Some steps of the algorithm, are set operations (union, difference, intersection, set-membership).

Can I assume them as $~ \mathcal{O}(1)$ operations? Have someone used them as $~\mathcal{O}(1)$ in his paper?

What minimum complexity should I assume for these operations? References are welcome.

$\endgroup$
  • 3
    $\begingroup$ There are many data structures that can be used to represent sets. Which is most appropriate depends on your exact circumstances, because different data structures trade the complexity of one operation against another. However, you cannot do all of these operations in constant time. For example, suppose you represent the elements of your set as linked lists: union is $O(1)$ but membership is $O(n)$. If you represent them as sorted arrays, membership is $O(\log n)$ but union increases to $O(n)$. Given this, I'm voting to close your question as too broad. $\endgroup$ – David Richerby Dec 7 '16 at 10:35
  • $\begingroup$ I suggest that you research data structures for sets on the internet and in textbooks. We'd be happy to answer more specific questions to help you understand those resources. $\endgroup$ – David Richerby Dec 7 '16 at 10:36
  • $\begingroup$ @DavidRicherby This seems like an answer to me. $\endgroup$ – Yuval Filmus Dec 7 '16 at 12:12
  • $\begingroup$ @YuvalFilmus Maybe. To me, it feels more like an explanation of why I can't answer. Also, I don't feel comfortable answering a question and voting to close it. (Though I guess your argument would be that, since I've provided an adequate answer, the question isn't too broad to answer.) $\endgroup$ – David Richerby Dec 7 '16 at 12:15

Your Answer

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

Browse other questions tagged or ask your own question.