Introduction

std::find_end searches for the last occurrence of one range inside another. For the ordinary iterator-based overload, the usual worst-case complexity is quadratic in the sense of O(N * M), where N is the length of the searched range and M is the length of the pattern range, although the exact bound is more precisely written in terms of comparisons and depends on the overload.

What std::find_end Does

The algorithm looks for the last subrange [s_first, s_last) that matches inside [first, last). It returns an iterator to the beginning of that last match, or last if no match exists.

A simple example:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> data{1, 2, 3, 1, 2, 3, 4};
7    std::vector<int> pattern{1, 2, 3};
8
9    auto it = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
10    if (it != data.end()) {
11        std::cout << std::distance(data.begin(), it) << "\n";
12    }
13}

This prints 3 because the last occurrence of 1,2,3 starts at index 3.

The Naive Worst-Case Bound

If the implementation checks each possible starting position and compares up to the full pattern length, the cost is roughly:

(N - M + 1) * M

That simplifies to O(N * M) in Big-O terms.

This is the standard high-level answer when people ask for the asymptotic complexity of the normal overload.

The intuition is simple:

• there are about N candidate start positions
• each can require up to M comparisons

So the worst case is a product.

A Concrete Worst-Case Style Example

Consider a range filled with repeated values and a pattern that almost matches many times before failing late.

1#include <algorithm>
2#include <iostream>
3#include <string>
4
5int main() {
6    std::string text = "aaaaaaaaab";
7    std::string pattern = "aaab";
8
9    auto it = std::find_end(text.begin(), text.end(), pattern.begin(), pattern.end());
10    if (it != text.end()) {
11        std::cout << std::distance(text.begin(), it) << "\n";
12    }
13}

In repetitive inputs like this, many candidate positions can trigger several character comparisons before the algorithm rules them out.

That is how the O(N * M) style worst case arises.

Why the Exact Standard Wording Is More Careful

The C++ standard usually describes complexity in terms of the number of predicate applications or comparisons rather than only a simplified Big-O formula.

That matters because:

• empty-pattern behavior is special
• iterator category may influence the implementation strategy
• searcher-based overloads can have different complexity characteristics

So the textbook Big-O answer is useful, but it is not the whole story.

Iterator Category and Implementation Freedom

For bidirectional iterators, an implementation may search from the back conceptually, which can improve practical behavior in some cases. But the usual general-purpose worst-case analysis still lands in the same O(N * M) family for the simple overload.

The key point is that std::find_end is not specified as using a specialized sublinear pattern-matching algorithm by default.

So unless you are using a different overload with an explicit searcher or library-specific optimization, you should assume the straightforward bound.

Empty Pattern Edge Case

If the pattern range is empty, std::find_end returns last. That special case is effectively constant-time once the implementation detects the empty pattern.

This does not change the general asymptotic result for non-empty patterns, but it is worth knowing because edge cases in standard algorithms often behave differently from the main path.

Searcher-Based Overloads Are a Different Question

In newer C++ code, there are searcher-based algorithms for pattern matching. If you switch to a searcher object that implements a more advanced strategy, the complexity discussion changes.

That is why it is important to distinguish:

• plain iterator overload of find_end
• searcher-based or specialized searching approaches

If the question is specifically about std::find_end in its usual form, O(N * M) is the safe answer.

Space Complexity

The ordinary algorithm uses constant extra space.

Space: O(1)

It works through iterators and comparisons without needing an auxiliary table in the usual case.

Common Pitfalls

A common mistake is assuming all standard searching algorithms are linear because some string-search algorithms are. std::find_end does not guarantee that kind of bound in its ordinary form.

Another issue is forgetting that find_end searches for the last match, not the first. The algorithmic goal changes how implementations traverse and track matches.

Developers also sometimes quote one exact formula without specifying whether the pattern is empty or whether they are talking about the basic iterator overload.

Finally, do not confuse practical average behavior with worst-case asymptotic complexity. Inputs with repeated near-matches can still trigger the higher bound.

Summary

• For the normal iterator-based overload, the usual worst-case complexity is O(N * M).
• A more precise view is roughly (N - M + 1) * M comparisons in the naive worst case.
• 'find_end searches for the last occurrence of a subrange, not the first.'
• Space usage is typically O(1).
• Searcher-based or specialized alternatives can have different complexity behavior.