Tag Archives: Logarithms

Big-O notation

Big-O notation compactly describes the running time of an algorithm. An algorithm’s efficiency in terms of its worst-case running time, which is the largest amount of time an algorithm can take given the most difficult input of a fixed size

For example, if your algorithm for sorting an array of n numbers takes roughly n2 operations for the most difficult dataset, we say that the running time of your algorithm is O(n2).

In reality, any number of operations, such as 1.5n2, n2 + n + 2, or 0.5n2 + 1; all these algorithms are O(n2) because big-O notation only cares about the term that grows the fastest with respect to the size of the input.

A function f(n) is Big-O of function g(n), or O(g(n)), when f(n) ≤ c · g(n) for some constant c and sufficiently large n.

Big O notation is to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. Read more of this post