CODEWITHSUNDEEP
c++stltime-complexity
etotheipi
etotheipi

Reputation: 49

Complexity of searching in a set of sets (C++)

I have a set of sets of positive integers std::set<set::<int> > X. Now I am given a set std::set<int> V and I want to know if it occurs in X. Obviously, this can be done by invoking the function find, so X.find(V) != X.end() should return true if V is in X.

My question is about the complexity of this operation, i.e. if X contains n sets of positive integers, what is time complexity of X.find(V)?

Upvotes: 0

Views: 879

Answers (2)

srt1104
srt1104

Reputation: 959

Suppose there are e sets in X such that the summation of sizes of all e sets is n, i.e., |S1| + |S2| + ... + |Se| = n then in the worst case X.find(V) will take O(m*log(e)) where m is the size of V, i.e., |V| = m. As you can see it is independent of n.

Why? So a set in STL is typically implemented as a self-balancing binary search tree. Therefore the height of root is always O(log(e)) where e is the total number of elements in the tree currently. Now notice that in our case the nodes of the tree are sets. set by default use less than < operator to compare with other set of the same type which takes O(min(|S1|, |S2|)) time to compare.

Therefore in the worst case, if the set V we want to find is one of the leaves of X and all the nodes on the branch from the root to V have size >= |V| then every node comparison will take O(|V|) time and since there are O(log(e)) nodes on this branch, it'll take us O(m*log(e)) time.

Upvotes: 0

Jesse Maurais
Jesse Maurais

Reputation: 153

Searching in a set is O(log n) in the number of elements, regardless of what the elements are composed of, even other sets. If the element is another set all you need is an ordering predicate (using the address of the object is a safe default). However, searching for an integer nested in the set of sets is going to be O(m log n) in general.

Upvotes: 1

Related Questions