CODEWITHSUNDEEP
c++boostcomplexity-theoryboost-mpl
mirt
mirt

Reputation: 1493

Boost.MPL complexity

The boost::mpl::push_back documentation states that:

push_back performs an insertion at the end of the sequence with guaranteed O(1) complexity.

Is it complexity of compilation time?

Upvotes: 2

Views: 152

Answers (2)

linyaa
linyaa

Reputation: 892

The O(1) refers to complexity during runtime. Usually, procedures which execute in O(1) time are said to execute in constant time. In this case, the documentation claims that the time needed for push_back to execute is constant with respect to the length of the list; that is, its execution time will be a fixed constant time independent of the list's length.

On the other hand, if the documentation had claimed that push_back executed with O(n) complexity, that would have indicated that push_back's execution time could be approximated by a linear function of the list's length, where the list's length here is n. Functions that fall in this complexity category are said to execute in linear time.

Wikipedia has a good introduction to the O(n) notation [1]. A good introductory text is "An Introduction to Algorithms" by Cormen, Lieverson, and Rivest.

Upvotes: 0

ForEveR
ForEveR

Reputation: 55897

Yes of course. It works with types, not with values.

The Boost.MPL library is a general-purpose, high-level C++ template metaprogramming framework of compile-time algorithms, sequences and metafunctions

Upvotes: 4

Related Questions