Complexity of std::count

Question

I was in some online code quiz website where there is a complexity restriction that the code should not exceed O(N) in both time and memory where N is the size of the vector A. My code was exactly (Full Code):

int foo(int X, const std::vector<int> &A) {
    auto N = A.size();
    auto total_hit = std::count(A.cbegin(), A.cend(), X);
    auto K = N - total_hit;
    if (K < 0 || K >= N){
        return -1;
    }
    return K;
}

I got a result that I exceed the time complexity. Is there any possibility rather than they are wrong?

Answer 1

According to the ref:

Complexity: exactly last - first comparisons / applications of the predicate

they are wrong!

And cplusplus agrees:

Complexity: Linear in the distance between first and last: Compares once each element.

---

Of course, the complexity of std::cbegin(), std::cend() and std::vector::size() is constant.

---

_{If I were you, I would contact the site, linking them to this question.}