Big O Notation with Examples

big o graph

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.

swagasoft

Fully stack(MEAN) software engineer with over five years of experience participating in the complete product development lifecycle of successfully launched applications. Eager and willing to deliver mission- critical technology solutions.

View all posts by swagasoft →

Leave a Reply

Your email address will not be published. Required fields are marked *