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?