Is it O(NlogN) or O(N^2)?

Question

I am trying to solve a problem on BinarySearch.com:

Given a list of integers nums sorted in ascending order and an integer k, return whether any two elements from the list add up to k. You may not use the same element twice. Note: Numbers can be negative or 0. This should be done in O(1) space.
So for nums = [1, 3, 5, 8] and k = 6, answer should be true.

I know it can be done using two pointers, but I am learning binary search, so I came up with the following logic:

bool solve(vector<int>& nums, int k) {
    for(int i=0; i<nums.size(); i++) {
        auto loc=lower_bound(begin(nums), end(nums), k-nums[i]);
        if(loc!=nums.end()) {
            if(distance(nums.begin(), loc)!=i && *loc+nums[i]==k) return true;
        }
    }
    return false;
}

It gets accepted, but what is the time complexity? I am not sure if it is O(NlogN) since I run binary search (an O(logN) algo) for each value in nums, or if it should be O(N^2) because when the if condition is true, I use distance(), which, as I understand, is an O(n) operation by itself.

Answer 1

As noted in comments in worst case the code iterates over the array and performs binary search on the array in each step. And so the complexity of that operation is O(Nlog(N)).

I use distance(), which, as I understand, is an O(n) operation by itself.

Actually it is O(1) when used on std::vector::iterator because it is a LegacyRandomAccessIterator ( Is std::next for vector O(n) or O(1)? ) and for such iterators std::distance is O(1) and so it doesn't participate in our calculation.