CODEWITHSUNDEEP
c++stringstlsettime-complexity
Minato
Minato

Reputation: 13

Time Complexity of inserting string to c++ stl set

What is the time complexity of inserting string to set container of c++ STL? According to me, it should be O(xlogn), where x is length of string to be inserted and n is size of set. Also copying of string to set should be of linear in length of string. But this code of mine is running instantly.

#include<bits/stdc++.h>
using namespace std;
int main(){

    set<string> c;
    string s(100000,'a');
    for(int i=0;i<100000;i++){
        c.insert(s);
    }

}

Where am I wrong, shouldn't the complexity be order of 10^10?

Upvotes: 1

Views: 3461

Answers (1)

rustyx
rustyx

Reputation: 85351

You should use the set in some way to reduce the risk of the loop getting optimized away, for example by adding return c.size();.

Also your choice of the number of iterations might be too low. Add a digit to the loop counter and you will see a noticeable run time.

A modern CPU can easily process >2*109 ops/s. Assuming your compiler uses memcmp, which is probably hand-vectorized, with a small working set such as yours you're working entirely from the cache and can reach throughput of up to 512 bytes per comparison (with AVX2). Assuming a moderate rate of 10 cycles per iteration, we can still compare >1010 bytes/s. So your program should run in <1 s on moderate hardware.

Try this updated code instead:

#include <string>
#include <set>
using namespace std;
int main(){

    set<string> c;
    string s(100000,'a');
    for(int i=0;i<1000000;i++) { // Add a digit here
        c.insert(s);
    }
    return c.size(); // use something from the set
}

With optimization on (-O3) this takes ~5 seconds to run on my system.

In other words yes, inserting into a binary tree has O(log n) complexity, but comparing a string has O(n) complexity. These n's aren't the same, in the case of a map it represents the map size, and in case of string - the length of the string.

In your particular case the map has just one element, so insertion is O(1). You get linear complexity O(n) purely from string comparisons, where n is string_length * number_of_iterations.

Upvotes: 1

Related Questions