Learning F# Functional Data Structures and Algorithms

Algorithmic complexity and the Big-O notation

Big-O notation provides a relative measure for complexity of an algorithm. In contrast with the theta (two-sided bound), Big-O is the upper bound of the complexity which, in layman terms, shows what would be the worst case scenario complexity based on the number of operations it would take.

The complexity of an algorithm is an important concept for developers to understand; if a problem can be addressed in a single pass, and your solution somehow addresses it in a nested loop, you have dramatically increased the number of operations, hence making your approach ultimately unusable for large scale problems.

There are various different classes of problems based on their algorithmic complexity; the lowest ...