Definition

Big O notation is used to describe the performance or complexity of an algorithm. It is about finding asymptotic upper bound.

Notation is a system of symbols to express technical facts or quantities.

Asymptotic means approaches a limit, usually infinity.

Let’s see an example. Here is a function to analyze:

1
2
3
4
for (i = 0; i < array.length; i++) {
for (i = 0; i < array.length; i++) {
}
}

Full count of iterations will be i2 and Big O notation for this code will be O(n2).

In calculations we care only about the dominant terms. For example, when function is n2 + 2, we will use only n2 and Big O will be O(n2).

Dominant term is the term that gets biggest as n gets bigger. Let’s see an example: n2 + n4. In this formula n4 will grows faster and it will be dominant term. Big O notation will be O(n4).

Most common Big O notations

Chart from bigocheatsheet.com

O(1)
This notation means constant time. Code example:

1
2
3
function logFirstElement(array) {
console.log(array[0]);
}

O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function binarySearch(array, target) {
let lowIndex = 0;
let highIndex = array.length - 1;
let middleIndex;

while (lowIndex <= highIndex) {
middleIndex = Math.floor((lowIndex + highIndex) / 2);
if(array[middleIndex] === target) {
return middleIndex;
}

if (target < array[middleIndex]) {
highIndex = middleIndex - 1;
} else {
lowIndex = middleIndex + 1;
}
}
return null;
}

O(n)

1
2
3
4
5
function logAllArrayElements(array) {
for (let i = 0; i < array.length; i++) {
console.log(array[i]);
}
}

O(n log n)

1
2
3
4
5
function multiDimentionalBinarySearch(arrayOfArrays, target) {
for (let i = 0; i < arrayOfArrays.length; i++) {
binarySearch(arrayOfArrays[i], target); // binarySearch from example above
}
}

O(n2)

1
2
3
4
5
6
7
function multiplyAllArrayElements(array) {
for (let i = 0; i < array.length; i++) {
for (let n = 0; n < array.length; n++) {
console.log(i * n);
}
}
}

O(2n)

1
2
3
4
5
6
7
function calculateFibonacci(number)
{
if (number <= 1) {
return num;
}
return calculateFibonacci(number - 2) + calculateFibonacci(number - 1);
}

O(n!)

1
2
3
4
5
function iterateRecursive(iterationCount) {
for(let i = 0; i < iterationCount; i++) {
iterateRecursive(iterationCount - 1);
}
}

All complexity notations

Big O (O()) describes the upper bound of the complexity.

Omega (Ω()) describes the lower bound of the complexity.

Theta (Θ()) describes the tight bound of the complexity, i.e. upper and lower bound.

Little O (o()) describes the upper bound excluding the exact bound.

Besides time complexity, Big O notation is used for memory complexity. It works similarly.