### What is Big O Notation?

Big O notation is a way to describe the complexity of a function. It can be used to calculate the time or memory requirements of a given function. To understand Big O notation, we need to understand the following terms:

### Basic definitions

| Term        | Definition                                    | Big O Notation |
| ----------- | --------------------------------------------- | -------------- |
| Constant    | A function that grows in a constant manner    | O(1)           |
| Linear      | A function that grows in a linear manner      | O(n)           |
| Logarithmic | A function that grows in a logarithmic manner | O(log n)       |
| Linearithmic| A function that grows in a linearithmic manner| O(n log n)     |
| Quadratic   | A function that grows in a quadratic manner   | O(n^2)         |
| Factorial   | A function that grows in a factorial manner   | O(n!)          |

We'll look at these in more detail in the next section, in order of complexity.

### Constant

`O(1)`

Constant functions are the simplest to understand and easiest to predict. They are functions that take the same amount of time to run regardless of the input size. If this function were to take `2ms` to run, it would always take `2ms` to run, regardless of the size of `n`. An example of this would be a function that takes in an array and returns the first element in the array.

```javascript
let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];

function constant(arr) {
  let x = arr[0];
  return x;
}
//example usage:
constant(n); //returns 2
```

### Linear

`O(n)`

The most basic Big O notation is `O(n)`. This means that the function grows directly with the size of the input. Let's say we have a function that takes an array of numbers and returns the sum of all of the numbers in the array. We can use this notation to calculate the time or memory requirements of this function. Here's what that would look like:

```javascript
let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
function linear(arr) {
  let result = 0;
  arr.map(function (i) {
    result += i;
  });
  return result;
}

//example usage:
linear(n); //returns 1026
```

For the function `linear`, the input size is `n`, and the output size is `n`. To put this literally, if each element in the array takes `4ms` to process, then the function will take `12ms` to process, due to the array being 3 elements long. For each additional element, the function will take `4ms` more to process.

### Logarithmic

`O(log n)`

A more rapidly growing Big O notation is `O(log n)`. An example of this would be a binary search function. This is a function that takes an array of numbers and returns the index of the number that is being searched for.

```javascript
let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];

function logarithmic(n, x) {
  let start = 0;
  let end = n.length - 1;
  let middle = Math.floor((start + end) / 2);

  while (n[middle] !== x && start <= end) {
    if (x < n[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  if (n[middle] === x) {
    return middle;
  } else {
    return -1;
  }
}
//example usage:
logarithmic(n, 4); //returns 2
```

### Linearithmic

`O(n log n)`

Continuing on, we have linearithmic growth. An example of this would be a merge sort function. This is a function that takes an array of numbers `n` and sorts them in ascending order. Breaking down the complexity, we can see that the function will grow in a linear manner depending on the size of the `n`, but will also increase in complexity logarithmically with `n`. This function grows rapidly, but is able to handle large inputs.

```javascript
let n = [1024, 256, 512, 128, 32, 64, 8, 16, 2, 4, 1, 0];

function mergeSort(n) {
  if (n.length <= 1) {
    return n;
  }
  let middle = Math.floor(n.length / 2);
  let left = n.slice(0, middle);
  let right = n.slice(middle);
  function merge(x, y) {
    let result = [];
    while (x.length && y.length) {
      if (x[0] < y[0]) {
        result.push(x.shift());
      } else {
        result.push(y.shift());
      }
    }
    return result.concat(x.slice()).concat(y.slice());
  }
  return merge(mergeSort(left), mergeSort(right));
}
//example usage:
mergeSort(n); //returns [1,2,4,8,16,32,64,128,256,512,1024]
```

### Quadratic

`O(n^2)`

Next we have Quadratic growth, expressed as `O(n^2)`. An example of this would be a bubble sort function, which is a function that takes an array of numbers and sorts them in ascending order. This function will take `n` elements and compare each element to every other element. This function grows rapidly and is not recommended for large inputs.

```javascript
let n = [1024, 256, 512, 128, 32, 64, 8, 16, 2, 4, 1];

let bubbleSort = (n) => {
  let l = n.length;
  for (let i = 0; i < l; i++) {
    for (let x = 0; x < l; x++) {
      if (n[x] > n[x + 1]) {
        let y = n[x];
        n[x] = n[x + 1];
        n[x + 1] = y;
      }
    }
  }
  return n;
};
//example usage:
bubbleSort(n); //returns [1,2,4,8,16,32,64,128,256,512,1024]
```

### Factorial

`O(n!)`

Nearing the most rapidly growing Big O notation is `O(n!)`. This means that the function grows in a factorial manner. An example of this would be a function that returns every possible combination of an array of numbers. This function would take `n` elements and return `n!` possible combinations. This function grows rapidly and is not recommended for large inputs.

```javascript
let n = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let counter = 0;
function permutations(n) {
  if (n.length <= 1) {
    return [n];
  }
  let result = [];

  for (let i = 0; i < n.length; i++) {
    let x = n.slice();
    let y = x.splice(i, 1);
    let z = permutations(x);
    for (let j = 0; j < z.length; j++) {
      counter++;
      result.push(y.concat(z[j]));
    }
  }
  return result;
}
//example usage:
permutations(n);
console.log(counter + " permutations"); //returns 32659200 permutations
```

### There's a catch

While this seems very straight forward, unknown datasets present a new challenge. In most real-world scenarios, a calculation would be done to determine the best case, worst case, and average scenerio. Take the following search function for example:

```javascript
let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
let counter = 0;
function search(n, x) {
  for (let i = 0; i < n.length; i++) {
    counter++;
    if (n[i] === x) {
      console.log("loops:", counter);

      return i;
    }
  }

  console.log("loops:", counter);
  return -1;
}

//example usage:
search(n, 1);
//returns loops: 1

search(n, 1024);
//returns loops: 12

search(n, 2048);
//returns loops: 23
```

With this example, the worst case scenario would be that every element gets iterated over before the target is found. This would be represented as `O(n)`. The best case scenario would be that the target is found at the beginning of the array. This would be represented as `O(1)`. When allocating resources, it is important to consider the worst case scenario and the frequency at which it may occur.

### Conclusion

While we have only covered the most commonly referenced notation types, there are many more to explore and learn about. For more information check out [This Release](https://cs50.harvard.edu/ap/2020/assets/pdfs/computational_complexity.pdf) from Harvard's CS50 materials.


Posts with tag ‘data-strucures’

A Basic Understanding of Big O Notation

How to understand Big O Notation Using Common Algorithms