### 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 | for (i = 0; i < array.length; i++) { |

Full count of iterations will be i^{2} and Big O notation for this code will be O(n^{2}).

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

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

### Most common Big O notations

Chart from bigocheatsheet.com

**O(1)**

This notation means constant time. Code example:

1 | function logFirstElement(array) { |

**O(log n)**

1 | function binarySearch(array, target) { |

**O(n)**

1 | function logAllArrayElements(array) { |

**O(n log n)**

1 | function multiDimentionalBinarySearch(arrayOfArrays, target) { |

**O(n ^{2})**

1 | function multiplyAllArrayElements(array) { |

**O(2 ^{n})**

1 | function calculateFibonacci(number) |

**O(n!)**

1 | function iterateRecursive(iterationCount) { |

### 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.