Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
Functions with constant time complexity, noted , will run and return their output in very similar amounts of time regardless of any other factors, such as number of elements in a container, size of a range evaluated, etc.
For example, the function
size() of a container always runs in a constant amount of time, regardless of the number of elements contained in the container.
That is because, in order to improve the speed of the function, we sacrifice some memory space, by storing a cached value of the number of elements. The function could be written in this way:
And fetching an integer value from a location in memory takes similar amount of time everytime, and it is not dependant on the number of element in the container.