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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ricardomol.gitbook.io/notes/comp-sci/big-o-notation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.