Time complexity in std::multiset

cpp
multiset
time-complexity

#1

accepted solution solution with TLE
The two given solutions, don’t have much difference, yet one gives TLE while other gets accepted very easily. I wonder why so ?
Does multiset.end( ) have a non-constant time complexity ?


#3

cin.tie(0);
cout.tie(0);

If you only include these lines in your TLE code, then your solution will get accepted.

No. end() does not have non-constant time complexity. It has constant time complexity.

See this. https://en.cppreference.com/w/cpp/container/multiset/end


#4

Thanks for this, though I had never seen such a huge time difference by just adding cin.tie(0) and cout.tie(0) ! I wonder what data-structure should be used to make the solution accepted without these two . :slight_smile: /


#5

I think the data structure is efficient enough but the in the codechef, for many programs we have to use fast i/o. Happened to me in last long contest. In problem SJ1 I didn’t use fast I/O and hence TLE was coming. But when I used fast i/o only I got it accepted.


#6

as we know that the implementation of multiset is in the form of r-b tree,and since the values stored in a tree are not in continuous memory locations therefore it takes O(N) time
per operation to traverse in worst case from one value to another…therefore it gives TLE…
check if u have used such library functions which have O(log N) complexity,since they will work in O(N) on implementing on multiset instead of O(log N) hence it is givingh TLE:)