CODEWITHSUNDEEP
algorithmc++11time-complexity
Damian
Damian

Reputation: 4631

complexity of minmax_element

How is minmax_element typically implemented? I can see the time complexity is at most max(floor(3/2(N−1)), 0) applications of the predicate, where N = std::distance(first, last).

Where minmax_element allows me to find the smallest and largest elements in a range of elements that can be iterated over (read: containers). For example:

#include <algorithm>
#include <vector>
using namespace std;

void Algorithm_minmax_element()
{
    double x = 2, y = 1, z = 0;
    vector<double> v = { 2, 1, 0, -1 };

    auto result1 = minmax(x, y);
    // result1 == pair(1, 2)
    auto result2 = minmax({ x, y, z });
    // result2 == pair(0, 2)
    auto result3 = minmax_element(v.begin(), v.end());
    // result3 == pair(&v[3] = -1, &v[0] = 2)
}

Upvotes: 1

Views: 422

Answers (1)

Lior Kogan
Lior Kogan

Reputation: 20618

A reference implementation is given in cppreference.com.

Using std::min and std::max for each element would require two comparisons per element, or 2n comparisons in total. Same goes for std::min_element and std::max_element.

The reference implementation requires only about 3n/2 comparisons in total. The principle is simple: at each step, we process 2 elements. We need one comparison to decide which one is smaller, one comparison to compare the smaller to the minimum, and one comparison to compare the larger to the maximum. Total of 3 comparisons for each 2 elements.

Upvotes: 1

Related Questions