> For the complete documentation index, see [llms.txt](https://ricardomol.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ricardomol.gitbook.io/notes/comp-sci/big-o-notation.md).

# Big O Notation

A **way to assess the speed  (performance)   of an algorithm**

Measures **how quickly the run-time grows relative to the input, as the input increases**.

We are concerned with the **number of operations a function performs.** Not the number of values it returns.

**Based on the maximum possible iterations**, even though the function *could* finish early**.**

A **measure of the “worst case scenario”**.

## Time Complexity vs Space Complexity

**Time complexity:** the amount of time taken by an algorithm to run relative to the length of the input.

We can also measure the efficiency of algorithms in terms of **space complexity: the amount of space or memory used by an algorithm relative to the length of the input**.

**Both can be described using Big O Notation**, and space complexity is bounded by time complexity. In other words, space and time complexity must be equal, or space complexity must be less.

## O(1)

Represents an **algorithm whose run-time is fixed**.

No matter the amount of data you feed in, the algorithm will always take the same amount of time.

Example:

```javascript
function(array) {
  return array[0];
}
```

## O(N) — Linear Time

As the length of the array increases, the amount of processing required increases *at the same rate*.

Example:

```javascript
function logArray(array) {
  for (let i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
}
```

**Big O Notation is based on the maximum possible iterations**. Because of that, the following function still has an algorithmic efficiency of O(N), **even though the function&#x20;*****could*****&#x20;finish early; that’s why some people see it as a measure of the “worst case scenario”**.

```javascript
function findTheMeaningOfLife(array){
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 42) {
      return i;
    }
  }
}
```

## O(N²) — Quadratic Time

An algorithm increases at ***twice the relative rate*** of O(N).&#x20;

Let’s say we have an array of three numbers: `array = [1, 2, 3]` .

If we pass that to the function `logArray()` above, then it will simply print out the numbers 1, 2 and 3.

But what about this function?

```javascript
function(array){
  for (let i = 0; i < array.length; i++){
    for (let j = 0; j < array.length; j++){
      console.log(array[j]);
    }
  }
}
```

## O(N³), O(N⁴) — Cubic Time, Quartic Time, and so on

If two nested loops gives us O(N²), it follows that three nested loops gives us O(N³), four nested loops gives us O(N⁴), and so on.

Let’s return to our simple array `[1, 2, 3]` , and pass it to the following with a performance of O(N³):

```javascript
function(array){
  for (let i = 0; i < array.length; i++){
    for (let j = 0; j < array.length; j++){
      for (let k = 0; k < array.length; k++){
        console.log(array[k]);
    }
  }
}
```

And so the pattern continues.

**As the powers increase, the run-time of each algorithm increases drastically at scale.**

## Why We Often Ignore Multiples

Let’s say for every item we put into our function, it processes the data twice over.

Example:

```javascript
function countUpThenDown(array) {

for (let i = 0; i < array.length; i++) {
    console.log(i);
  };
for (let i = array.length; i > 0; i--) {
    console.log(i);
  };
}
```

**We&#x20;*****could*****&#x20;call that O(2N)**.&#x20;

**At small scales, the difference is very important. But Big O Notation is concerned with how an algorithm functions at a very high scale. For that reason, we tend to ignore multiples.**

## Why We Often Ignore All But the Biggest Power

**For the exact same reason**, you’ll rarely see a function’s efficiency described as O(N² + N).

In most situations it is enough to reduce expressions to the element that has the biggest impact on the algorithm as it scales.

Example:

&#x20; `O(2N³ + 5N² + 4N + 7)` will be reduced to `O(N³)`

## O(logN) — Binary Search

One of the most common and fastest search algorithms, the so-called “**Binary Search**” , has an efficiency of **O(logN)**.

As more data is processed by a Binary Search function, the amount of processing time increases by a factor of logN.

Every time you double the data-set, an algorithm with performance O(logN) only has to add in 1 more step.&#x20;