Proposed resolution:

Change the complexity to "At most (last - first) applications of the corresponding predicate".

template<class ForwardIterator, class Size, class T> 
  ForwardIterator 
    search_n(ForwardIterator first , ForwardIterator last , Size count , 
             const T& value ); 

template<class ForwardIterator, class Size, class T, 
         class BinaryPredicate> 
  ForwardIterator 
    search_n(ForwardIterator first , ForwardIterator last , Size count , 
             const T& value , BinaryPredicate pred );

Complexity: At most (last - first ) * count applications of the corresponding predicate if count is positive, or 0 otherwise.