Algorithm for checking if an element is in a vector that is not O(n)

I need to be quick about this, As I don't have much time today.
But the Standard Library mentioned that the contains() function is O(n).

Is there a better way to do this? (at least not linear time)

If the vector is sorted, you can use binary_search, which takes O(log 𝓃) time. Otherwise, O(𝓃) is the best you can theoretically achieve.

2 Likes

Have you considered alternative collections? A HashSet can do it in O(1).

8 Likes

Also check your dataset sizes (typical and worst-case). I'd rather have a simple and efficient O(n) with a smallish n than an O(1) with a big constant cost.

As always, benchmark.

8 Likes

I can't remember the exact talk, but several years ago there was a talk at CppCon showing the relative performance of different data structures. The big thing I took away was that linearly scanning std::vector (Vec) was faster than std::map (BTreeMap) up to a surprisingly large number of elements despite worse algoritmic complexity because modern CPUs really like scanning through memory sequentially.

6 Likes

Exactly ! I know people that abuse the O(x)-ness of their algorithms without realizing that in real life cache-trashiness is often more important than how many loops you imbricate. Basically once you've pulled a cache line what you do inside it is O(zero), and smart programmers take advantage of that.

6 Likes