Time complexity of std::lower_bound and std::upper_bound

I use std::upper_bound on a sorted vector, and it's clearly not working in logarithmic time, as I compare it with my own implementation of upper bound search. Why is it happening? My code:

for (size_t i = 1; i < sorted_vector.size(); ++i) {
    size_t m = std::upper_bound(
        sorted_vector.begin(),
        sorted_vector.begin() + i,
        values_to_search[i]);

Total time here supposed to be O(n * log(n)). When I use my own implementation of upper_bound on an array of size 50000 it takes about 0.05 seconds, while with std it's around 3 seconds.