Efficient C++ Performance Programming Techniques

Asymptotic Complexity

The asymptotic complexity of an algorithm is an approximation of algorithm performance. It is a mapping from the set of algorithms to a special set of performance levels. If you sum up the elements of a vector of N integers, you have to inspect each integer once, and only once, so the complexity is of the order of N, and we call it O(N). Suppose, on the other hand, that you are building a vector of N elements and for some reason you chose to insert them in the front of the vector. Every element insertion at the front of a vector forces the shift of all existing elements by 1. This results in (1+2+3+...+N) overall shifts of vector elements, which is (N/2)(N+1) shifts. Even though we have (N*N/2)+(N/2) shifts we still say ...