4

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).

curiousguy
  • 8,038
  • 2
  • 40
  • 58

4 Answers4

7

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.

sebrockm
  • 5,733
  • 2
  • 16
  • 39
  • If it isn't meaningful in theory but only in engineers' feelings, we can't be sure to be able to apply all the math toolbox, that applies to math concepts, not intuitions. – curiousguy Nov 01 '19 at 01:43
  • 2
    @curiousguy: Where is the meaning in declaring that all algorithms are O(1) on a finite machine? Even if it is technically accurate, *it says absolutely nothing of value.* Whereas saying that a bubble sort is O(n^2) while quick-sort is O(nlog(n)) may not be technically true for a finite machine, it is a far more *useful* statement about those algorithms. Declaring that `std::sort` shall be at least O(nlog(n)) means that it cannot be a bubble sort. And if you implement it as such, and try to defend it with "it's O(1) on a finite machine", people will still call your implementation *broken*. – Nicol Bolas Nov 01 '19 at 03:08
  • @NicolBolas "_declaring that all algorithms are O(1) on a finite machine_" I'm not promoting that idea. I take issue with intuitive but incorrect math statement as you can't use all the math tools on these w/o getting paradoxes. And I accept the fact that forbidding bubble sort impl is useful. – curiousguy Nov 01 '19 at 03:17
  • 1
    @curiousguy: The point this answer is making is that C++ operations (relative to the abstract machine which is the only thing that matters) are neither finite nor bounded, and therefore your question of how C++ squares that circle is irrelevant. The C++ standard is compatible with computer science and math. Where are these supposed paradoxes? – Nicol Bolas Nov 01 '19 at 03:21
  • @NicolBolas What is the "abstract machine"? – curiousguy Nov 01 '19 at 04:08
  • @curiousguy: [It's here.](https://timsong-cpp.github.io/cppwp/n4659/intro.execution#1) – Nicol Bolas Nov 01 '19 at 04:21
  • @NicolBolas "_Certain aspects and operations of the abstract machine are described in this International Standard as implementation-defined (for example, sizeof(int))_" So it looks like the abstract machine has finite length integer types and is "bounded". – curiousguy Nov 01 '19 at 04:23
  • @curiousguy: I fail to see how the size of an integer has anything to do with asymptotic complexity as used by the C++ standard. That is, when does the standard state the complexity of an operation relative to the number of bytes in an integer? – Nicol Bolas Nov 01 '19 at 04:25
  • @NicolBolas If integers are bounded, then so are arrays indexed by integers, or any container with a size expressed by that integer type (which can be larger than type `int` but which is still bounded). Same for pointers are they are trivial types and can only have so many diff values. – curiousguy Nov 01 '19 at 04:33
  • @curiousguy: But what does that have to do with asymptotic complexity? The complexity of an algorithm is the complexity of that algorithm *regardless* of whether the actual inputs to that algorithm are "bounded" or not. That's a function of math, not of implementation. – Nicol Bolas Nov 01 '19 at 04:51
  • @NicolBolas C++ code isn't an abstracted "algorithm"; it's a real function with C++ datatypes. Mathematical C++-free "algorithms" are not the subject of the C++ std. – curiousguy Nov 01 '19 at 04:55
  • 1
    @curiousguy: "*it's a real function with C++ datatypes*" A real function with real C++ datatypes that implements a real *algorithm* that is subject to the CS concept of complexity. Either that is true, or a C++ implementation of bubble sort is O(1). Which is it? – Nicol Bolas Nov 01 '19 at 05:00
  • @NicolBolas The function is not the algorithm. It's a particular practical application of the algorithm, with specific limits. The std does not describe "algorithms". There is no "algorithm" section in the specification of any C++ std lib function. – curiousguy Nov 01 '19 at 05:16
  • 1
    @curiousguy: So if you're at work, and you get the task to write an O(nlog(n)) sort function, are you going to tell your boss "well, I'd love to, but functions aren't algorithms and therefore don't have algorithmic complexity, so even though it's obvious to everyone involved what you asked me to do, I'm not going to do it because of a technicality." – Nicol Bolas Nov 01 '19 at 05:21
  • @NicolBolas Summary of your position: "math and logic = a technicality". And "functions aren't algorithms" is your position, not mine! I don't make that distinction as abstract algorithms don't exist. **All algorithms exist in some formal language and no formal language was specified in the C++ to describe these.** – curiousguy Nov 01 '19 at 05:27
  • @curiousguy *"If it isn't meaningful in theory but only in engineers' feelings, we can't be sure to be able to apply all the math toolbox"* If you really want to go this logical pathway, then have to do it *everywhere*, not only regarding C++ and hardware. That would mean that you cannot apply math *anywhere* in reality. Why? Because, just as hardware, the observable universe is **limited** (both, in size and number of particles inside). Maths uses the **concept** of infinity everywhere, but in reality it simply doesn't exist, so you cannot use maths in reality. – sebrockm Nov 01 '19 at 10:00
  • @sebrockm I have no idea what you are trying to say. What is the contradiction? Why can't you use math? – curiousguy Nov 01 '19 at 10:34
  • @curiousguy if I understood you correctly, you are saying "C++ is finite, so you cannot apply math tools that use the concept of infinity", right? I am saying: Not only C++ is finite, but the entire universe is, so you cannot apply math tools that use the concept of infinity. – sebrockm Nov 01 '19 at 10:38
  • @curiousguy I've just realized you updated your question, so I addressed that in my answer. Have a look :) – sebrockm Nov 01 '19 at 12:20
2

asymptotic complexity is a mathematical construct based on asymptotic behavior when the size of inputs and the values of numbers tend to infinity.

Correct. Similarly, algorithms are abstract entities which can be analyzed regarding these metrics within a given computational framework (such as a Turing machine).

C++ tries to use the concept of time complexity in the specification of many library functions

These complexity specifications impose restrictions on the algorithm you can use. If std::upper_bound has logarithmic complexity, you cannot use linear search as the underlying algorithm, because that has only linear complexity.

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

Obviously, any computational resource is finite. Your RAM and CPU have only finitely many states. But that does not mean everything is constant time (or that the halting problem is solved).

It is perfectly reasonable and workable for the standard to govern which algorithms an implementation can use (std::map being implemented as a red-black-tree in most cases is a direct consequence of the complexity requirements of its interface functions). The consequences on the actual "physical time" performance of real-world programs are neither obvious nor direct, but that is not within scope.

Let me put this into a simple process to point out the discrepancy in your argument:

  1. The C++ standard specifies a complexity for some operation (e.g. .empty() or .push_back(...)).

  2. Implementers must select an (abstract, mathematical) algorithm that fulfills that complexity criterion.

  3. Implementers then write code which implements that algorithm on some specific hardware.

  4. People write and run other C++ programs that use this operation.

You argument is that determining the complexity of the resulting code is meaningless because you cannot form asymptotes on finite hardware. That's correct, but it's a straw man: That's not what the standard does or intends to do. The standard specifies the complexity of the (abstract, mathematical) algorithm (point 1 and 2), which eventually leads to certain beneficial effects/properties of the (real-world, finite) implementation (point 3) for the benefit of people using the operation (point 4).

Those effects and properties are not specified explicitly in the standard (even though they are the reason for those specific standard stipulations). That's how technical standards work: You describe how things have to be done, not why this is beneficial or how it is best used.

Max Langhof
  • 23,383
  • 5
  • 39
  • 72
  • How can anything not be "constant time"? – curiousguy Oct 31 '19 at 11:08
  • 3
    @curiousguy we ignore the fact that computers are not infinite. In the region we are interested in, they exhibit the behaviours as described. – Caleth Oct 31 '19 at 11:19
  • @Caleth I see, it's a good physical approximation... it isn't the pure mathematical definition though. – curiousguy Oct 31 '19 at 11:22
  • "Anything is constant time for a sufficiently large constant" is unhelpfully reductive. Comparing the way things scale over finite inputs is still useful for anyone satisfied merely to achieve actual computations before the heat death of the universe. – Useless Oct 31 '19 at 11:46
1

Computational complexity and asymptotic complexity are two different terms. Quoting from Wikipedia:

Computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.

For time complexity, the amount of resources translates to the amount of operations:

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

In my understanding, this is the concept that C++ uses, that is, the complexity is evaluated in terms of the number of operations. For instance, if the number of operations a function performs does not depend on any parameter, then it is constant.

On the contrary, asymptotic complexity is something different:

One generally focuses on the behavior of the complexity for large n, that is on its asymptotic behavior when n tends to the infinity. Therefore, the complexity is generally expressed by using big O notation.

Asymptotic complexity is useful for the theoretical analysis of algorithms.

Daniel Langr
  • 22,196
  • 3
  • 50
  • 93
  • 1) I agree that f.ex. an STL algo can be described in term of elementary user provided < and copy operations, not fundamental C++ scalar or memory access operations. 2) The Q is about asymptotic specification in the std lib (mostly in the STL). – curiousguy Oct 31 '19 at 11:04
  • @curiousguy Where does the C++ Standard (std lib/STL) refer to _asymptotic_ specification? AFAIK, [there is no such thing](http://eel.is/c++draft/library#structure.specifications-3.10). In C++17 Draft, there is not a single occurrence of the word _"asymptotic"_. I don't think it uses _big O_ notation either. – Daniel Langr Oct 31 '19 at 11:06
  • It's pretty much the consensus, everywhere, that it's asymptotic complexity... I'm pretty sure the C++ committee thinks that. – curiousguy Oct 31 '19 at 11:11
  • 2
    "the complexity is evaluated in terms of the number of operations". This is not always the case. For some operations the complexity is stated to be "constant time" or "linear". This can only be understood as asymptotic complexity, even though the word "asymptotic" is not uttered. – n. m. could be an AI Oct 31 '19 at 11:30
0

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

There is none.

E_net4
  • 27,810
  • 13
  • 101
  • 139
n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243