O'Reilly logo

Efficient C++ Performance Programming Techniques by David Mayhew, Dov Bulka

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required