Why does it bother to provide two implementations for std::partition?

The C++ standard requires std::partition to have different numbers of predicate applications between ForwardIterator and BidirectionalIterator. For the ForwardIterator version, the number of predicate applications shall be <= N, where N = std::distance(first, last), but for the BidirectionalIterator version, the number of predicate applications shall be <= N/2. Obviously, both versions have time complexity O(N).

My question is, why does it bother to provide different requirements for different type of iterators? Such requirement forces a lot of compilers, e.g. MSVC, implement the function std::partition in two ways to meet such requirement, which does not seem to be very elegant.

A further question: Are there any algorithm that relies on this coefficient, such that when N/2 becomes N, the asymptotic complexity will be different? For my understanding, if we consider the Master's Theorem, for the form in T(n) = aT(n/b) + f(n), the coefficient in f(n) does not matter much.

C.f. An equivalent implementation of MSVC's partition:

template<class BidirIt, class UnaryPred>
BidirIt partition(BidirIt first, BidirIt last, UnaryPred pred, std::bidirectional_iterator_tag)
{
    while (true)
    {
        while ((first != last) && pred(*first))
        {
            ++first;
        }
        if (first == last)
        {
            break;
        }
        --last;
        while ((first != last) && !pred(*last))
        {
            --last;
        }
        if (first == last)
        {
            break;
        }
        std::iter_swap(first, last);
        ++first;
    }
    return first;
}
template<class ForwardIt, class UnaryPred> 
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred, std::forward_iterator_tag)
{
    first = std::find_if_not(first, last, pred);
    if (first == last)
    {
        return first;
    }

    for (ForwardIt src = std::next(first); src != last; ++src)
    {
        if (pred(*src))
        {
            std::iter_swap(first, src);
            ++src;
        }
    }
    return first;
}
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred)
{
    return partition(first, last, pred, typename std::iterator_traits<ForwardIt>::iterator_category());
}