CODEWITHSUNDEEP
c++algorithmstlsetcomplexity-theory
iloahz
iloahz

Reputation: 4561

What's the time complexity of std::lower_bound with std::set?

I know that there is std::set::lower_bound and the time complexity is O(log), and i see that std::lower_bound is much slower than std::set::lower_bound when operates on std::set.

I googled and found this:

http://en.cppreference.com/w/cpp/algorithm/lower_bound http://en.cppreference.com/w/cpp/iterator/advance

so it's clear that because of the std::advance is linear for set::iterator, the whole std::lower_bound takes up to O(n).

However, it runs much faster than O(n) when i use it(and so did some friends say), can anybody explain why or tell me it's just not like that.

Upvotes: 5

Views: 16245

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299880

TL;DR: whenever a container provides a method of the same name that an existing algorithm, it does so because the internal implementation is faster (relying on the container's properties) and thus you should just use it.

The problem is that complexity is fickle: O(N) what ?

The complexity guarantees on non-random-access iterators are:

  • O(N) iterations
  • O(log2(N)) comparisons

Depending whether iteration or comparison is the bottleneck, this actually changes everything!

In theory, in the case of sorted associative containers, one could wish to specialize std::lower_bound to take advantage of the fact that data is already sorted; however in practice it is relatively difficult. The major issue is that there is no telling that the comparison predicate of the set and that passed to lower_bound are indeed one and the same, and thus the algorithm need assume it is not the case (unless proven otherwise). And because the algorithm takes iterators instead of ranges/container, proving otherwise is left as an exercise for the reader.

Upvotes: 1

Dietmar Kühl
Dietmar Kühl

Reputation: 153840

The guaranteed complexity for std::lower_bound() is O(n) on non-random-access iterators. If this algorithm detects that the search is on an ordered associative container, it may take advantage of the tree structure possibly achieving a better conplexity. Whether any implementation does so, I don't know.

Upvotes: 3

Related Questions