Order Notation in Practice

By Roger Orr

Many of us are familiar with the "Big O" order notation for giving an idea of the complexity of algorithms; for example the C++ std::sort function is described as "N logN". But sometimes this can seem a little unconnected to the task of actually writing code.

I'll use some examples where there are multiple ways (with different complexity measures) of solving the same problem to explore a few questions, such as:

- What does complexity notation actually mean?

- What does this measure *not* tell us?

- How important is this in practice?

- What other considerations are also important to consider?