Is there any consistent definition of time complexity for real world languages like C++?

Question

C++ tries to use the concept of time complexity in the specification of many library functions, but asymptotic complexity is a mathematical construct based on asymptotic behavior when the size of inputs and the values of numbers tend to infinity.

Obviously the size of scalars in any given C++ implementation is finite.

What is the official formalization of complexity in C++, compatible with the finite and bounded nature of C++ operations?

Remark: It goes without saying that for a container or algorithm based on a type parameter (as in the STL), complexity can only be expressed in term of number of user provided operations (say a comparison for sorted stuff), not in term of elementary C++ language operations. This is not the issue here.

EDIT:

Standard quote:

4.6 Program execution [intro.execution]

1 The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.

2 Certain aspects and operations of the abstract machine are described in this International Standard as implementation-defined (for example, sizeof(int)). These constitute the parameters of the abstract machine. [...]

The C++ language is defined in term of an abstract machine based on scalar types like integer types with a finite, defined number of bits and only so many possible values. (Dito for pointers.)

There is no "abstract" C++ where integers would be unbounded and could "tend to infinity".

It means in the abstract machine, any array, any container, any data structure is bounded (even if possibly huge compared to available computers and their minuscule memory (compared to f.ex. a 64 bits number).

Answer 1

Obviously the size of scalars in any given C++ implementation is finite.

Of course, you are correct with this statement! Another way of saying this would be "C++ runs on hardware and hardware is finite". Again, absolutely correct.

However, the key point is this: C++ is not formalized for any particular hardware. Instead, it is formalized against an abstract machine.

As an example, sizeof(int) <= 4 is true for all hardware that I personally have ever programmed for. However, there is no upper bound at all in the standard regarding sizeof(int). What does the C++ standard state the size of int, long type to be?

So, on a particular hardware the input to some function void f(int) is indeed limited by 2^31 - 1. So, in theory one could argue that, no matter what it does, this is an O(1) algorithm, because it's number of operations can never exceed a certain limit (which is the definition of O(1)). However, on the abstract machine there literally is no such limit, so this argument cannot hold.

So, in summary, I think the answer to your question is that C++ is not as limited as you think. C++ is neither finite nor bounded. Hardware is. The C++ abstract machine is not. Hence it makes sense to state the formal complexity (as defined by maths and theoretical CS) of standard algorithms.

Arguing that every algorithm is O(1), just because in practice there are always hardware limits, could be justified by a purely theoretical thinking, but it would be pointless. Even though, strictly speaking, big O is only meaningful in theory (where we can go towards infinity), it usually turns out to be quite meaningful in practice as well, even if we cannot go towards infinity but only towards 2^32 - 1.

UPDATE:

Regarding your edit: You seem to be mixing up two things:

1. There is no particular machine (whether abstract or real) that has an int type that could "tend to infinity". This is what you are saying and it is true! So, in this sense there always is an upper bound.
2. The C++ standard is written for any machine that could ever possibly be invented in the future. If someone creates hardware with sizeof(int) == 1000000, this is fine with the standard. So, in this sense there is no upper bound.

I hope you understand the difference between 1. and 2. and why both of them are valid statements and don't contradict each other. Each machine is finite, but the possibilities of hardware vendors are infinite.

So, if the standard specifies the complexity of an algorithm, it does (must do) so in terms of point 2. Otherwise it would restrict the growth of hardware. And this growth has no limit, hence it makes sense to use the mathematical definition of complexity, which also assumes there is no limit.