Detour : Big-O Notation

Running time of an algorithm

Computer scientists typically measure an algorithm’s efficiency in terms of its worstcase running time, which is the largest amount of time an algorithm can take for the most difficult input of a given size. The advantage to considering the worst-case running time is that we’re guaranteed that our algorithm will never behave worse than our worst-case estimate.

Big-O notation compactly describes the running time of an algorithm. For example, if your algorithm for sorting an array of n numbers takes roughly $n^{2}$ operations for the most difficult dataset, then we say that the running time of your algorithm is $O(n^{2}$). In reality, depending on your implementation, it may use any number of operations, such as $1.5n^{2}$, $n^{2}$ + $n + 2$ ...