What is big o notation?

Big-O notation measures the worst complexity of the algorithm. With Big-O

Notation n represents the number of entries. The questions asked at Big-O are

Next: “What happens when infinity approaches?”

The Big-O notation is important when implementing the algorithm.

How efficient is the algorithm?

This tutorial focuses on big o notation with examples, therefore let me go straight to examples.

## big o notation examples

**1. O(1) – Constant Time**

O(1) is referred to as constant because The input space remains unchanged.

**An example of the O (1) algorithm is :**

- Find if a number is even or odd.
- Access element with an array index.
- Print the first element in a list.
- Find the value of a map.

.

Consider the following example Odd or Even of O(1)

```
function isEvenOrOdd(n) {
return n % 2 ? 'Odd' : 'Even';
}
console.log(isEvenOrOdd(10)); // => Even
console.log(isEvenOrOdd(10001)); // => Odd
```

It doesn’t matter if n is 10 or 10,001. Execute the second line once.

Another Example is Frequency Counter

```
const myObj = {the: 342, be: 333, and: 548, of: 50343, a: 4483, in: 212, to: 33 /* ... */};
function getWordFrequency(dictionary, word) {
return myObj[word];
}
console.log(getWordFrequency(myObj, 'the'));
console.log(getWordFrequency(myObj, 'in'));
```

Event if **myObj** has one million values, it will execute return **myObj[word] **only once. The run time complexity of the example above is O(1)

**2. O(n) – Linear time**

O(n) is referred to as linear time because the value of n is not constant. N can be 5 or 10,0000. The linear time complexity O (n) means that as the input increases, it takes a proportional amount of time to complete the algorithm.

**Examples of Linear Time Algorithm**

- Print all the values in a list.
- Find a giving element in a collection.

Print all values in the list below.

```
function exampleLinear(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i);
}
}
```

The largest item on an unsorted array

function findMax(n) {

let max;

let counter = 0;

for (let i = 0; i < n.length; i++) {

counter++;

if(max === undefined || max < n[i]) {

max = n[i];

}

}

console.log(`n: ${n.length}, counter: ${counter}`);

return max;

}

**3. O(n^2) – Quadratic time**

The growth rate of a function with quadratic time complexity is n2. If the input is size 2, perform four operations. If the input is size 8, it will cost 64, and so on.

**examples of quadratic algorithms**:

- A for loop running inside another for loop.
- Check if a collection has duplicated values.
- Sorting items in a collection using bubble sort, insertion sort, or selection sort.
- Find all possible ordered pairs in an array.

Example of for loop running inside another for loop

```
function exampleQuadratic(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i);
for (var j = i; j < n; j++ ) {
console.log(j);
}
}
}
```

Has duplicates

```
function hasDuplicates(n) {
const duplicates = [];
let counter = 0; // debug
for (let outter = 0; outter < n.length; outter++) {
for (let inner = 0; inner < n.length; inner++) {
counter++; // debug
if(outter === inner) continue;
if(n[outter] === n[inner]) {
return true;
}
}
}
console.log(`n: ${n.length}, counter: ${counter}`); // debug
return false;
}
```

Use counter variables to help with validation. The hasDuplicates feature has two loops. If there is a 4-word input, the internal block is output 16 times. If 9, the counter runs 81 times.

Bubble sort

```
function sort(n) {
for (let outer = 0; outer < n.length; outer++) {
let outerElement = n[outer];
for (let inner = outer + 1; inner < n.length; inner++) {
let innerElement = n[inner];
if(outerElement > innerElement) {
// swap
n[outer] = innerElement;
n[inner] = outerElement;
// update references
outerElement = n[outer];
innerElement = n[inner];
}
}
}
return n;
}
```

**4. O(n ^3 ) Quadratic time**

O(n^ 3) is called quadratic time because the list N is running concurrently.

Examples of O(n ^ 3)

- CubicLoop
- TrippleSum
- find xyz

Cublic Loop below

```
function exampleCubic(n) {
for (var i = 0 ; i < n; i++ ) {
console.log(i);
for (var j = i; j < n; j++ ) {
console.log(j);
for (var k = j; j < n; j++ ) {
console.log(k);
}
}
}
}
```

Tripple Sum

```
function tripletSum(x, a) {
for(var i = 0; i < a.length; i++) {
for(var j = i + 1; j < a.length; j++) {
for(var k = j + 1; k < a.length; k++) {
if((a[i] + a[j] + a[k]) === x) {
return true;
}
}
}
}
return false;
}
```

find xyz

```
function findXYZ(n) {
const solutions = [];
for(let x = 0; x < n; x++) {
for(let y = 0; y < n; y++) {
for(let z = 0; z < n; z++) {
if( 3*x + 9*y + 8*z === 79 ) {
solutions.push({x, y, z});
}
}
}
}
return solutions;
}
console.log(findXYZ(10)); // => [{x: 0, y: 7, z: 2}, ...]
```

**5. O(log n) – Logarithmic time**

The complexity of logarithmic time generally applies to algorithms that divide the problem in half each time. An example of O(log n) is the binary search algorithm.

Binary search

```
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
while (min <= max){
guess = Math.floor((max + min) / 2)
if(array[guess] === targetValue){
return guess;
}else if(array[guess] < targetValue){
min = guess + 1;
}else{
max = guess - 1;
}
}
return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
var result = doSearch(primes, 73);
```

As you can see, the above example divides them into two and uses the part that may likely have its target. You may be interested in the implementation of binary search. I have written how to implement binary search step by step.

6. O(n log n) – Linearithmic

The complexity of linear time is a bit slower than the linear algorithm. However, it is still much better than the quadratic algorithm (see the figure at the top of this page).

**Examples of Linearithmic algorithms:**

- Efficient sorting algorithms like merge sort, quicksort, and others.

```
/**
* Sort array in asc order using merge-sort
* @example
* sort([3, 2, 1]) => [1, 2, 3]
* sort([3]) => [3]
* sort([3, 2]) => [2, 3]
* @param {array} array
*/
function sort(array = []) {
const size = array.length;
// base case
if (size < 2) {
return array;
}
if (size === 2) {
return array[0] > array[1] ? [array[1], array[0]] : array;
}
// slit and merge
const mid = parseInt(size / 2, 10);
return merge(sort(array.slice(0, mid)), sort(array.slice(mid)));
}
/**
* Merge two arrays in asc order
* @example
* merge([2,5,9], [1,6,7]) => [1, 2, 5, 6, 7, 9]
* @param {array} array1
* @param {array} array2
* @returns {array} merged arrays in asc order
*/
function merge(array1 = [], array2 = []) {
const merged = [];
let array1Index = 0;
let array2Index = 0;
// merge elements on a and b in asc order. Run-time O(a + b)
while (array1Index < array1.length || array2Index < array2.length) {
if (array1Index >= array1.length || array1[array1Index] > array2[array2Index]) {
merged.push(array2[array2Index]);
array2Index += 1;
} else {
merged.push(array1[array1Index]);
array1Index += 1;
}
}
return merged;
}
```

**7. O(2^n) – Exponential time**

Exponential (base 2) working time means that each larger the input, the more calculations the algorithm performs.

**Examples of exponential runtime algorithms:**

- Power Set: finding all the subsets on a set.
- Fibonacci.
- Traveling salesman problem using dynamic programming.

Power Set

```
function powerset(n = '') {
const array = Array.from(n);
const base = [''];
const results = array.reduce((previous, element) => {
const previousPlusElement = previous.map(el => {
return `${el}${element}`;
});
return previous.concat(previousPlusElement);
}, base);
return results;
}
```

Conclussion

Some Big notation are not covered here, if you want to learn more, I urge you to take the course at khan Academy.