DS&A

‘Big O’ Notation

By making a series of assumptions and considering only “large” inputs, we can analyse how efficient an algorithm is without actually running it. The result of this analysis is a mathematical formula called the complexity (or time complexity) of the algorithm. For example, we derived the formula n² for the selection sort algorithm.

Using standard notation, we would say that selection sort’s complexity is O(n²), or that selection sort is an O(n²) algorithm.

This formula says, very roughly, how much “work” the algorithm has to do as a function of n, which represents the “input size”. In this post, we’ll see how to make sense of this formula, and how to derive it with as little algebra as possible.

• Tags: 
• big O notation, efficiency, complexity, static analysis, algorithms

• Read more
• Comments (0)