Cppreference's complexity?

Question

I am starting to understand notations of algorithmic time complexity, like the "big O". However, I do not understand many of the descriptions of different algorithmic complexities on cppreference, like for std::search. It does not involve the notations that I have finally learnt, such as "big O" and "big Omega".. How should I interpret complexity descriptions like this?

At most S*N comparisons where S = std::distance(s_first, s_last) and N = std::distance(first, last).

Answer 1

It means exactly what is written. It will do no more then S*N comparisons for inputs of lengths S and N. e.g if you have arrays of length 5 and 3 it will do no more then 15 comparisons:

std::array<char, 3> a;
std::array<char, 5> b;
std::search(b.begin(), b.end(), a.begin(), a.end());

Answer 2

The problem is that big O notation describes the asymptotic upper bound on complexity, and generally just the way complexity scales with respect to a single variable. Where there are multiple variables, they're assumed to be independent, and they all tend to infinity together.

It doesn't describe the exact number of operations for small values of N, or provide any way to describe functions with multiple types of operation which may have different runtime cost, and if you have multiple but non-independent variables it doesn't show their relationship until you reduce the form yourself.

In this case, you have two variables, and the asymptotic complexity depends on which of them are varying, and which dominates. So, we can call it O(S*N), but in these examples we could do better:

1. I'm searching for a fixed-length sub string in ever-longer source string. In this case S remains constant and so O(S*N) ≃ O(N) as N→∞.
2. I'm searching for a fractional subset of my ever-longer source string, say S = N/K for some constant K. Now I'm interested in O(S*N) = O(N²/K) ≃ O(N²) as N→∞.

So the description

At most S*N comparisons where S = std::distance(s_first, s_last) and N = std::distance(first, last).

is much more informative than O(S*N), and not only because it applies to all S and N rather than only to "sufficiently large" values.