Algorithms complexity

A summary of different algorithm complexities and examples, ordered from the most to the least efficient.

1. O(1) - Constant

The algorithm's runtime or space usage remains constant regardless of the size of the input. For example by accessing an element in an object by its key:

const animalsAndSounds = {
  dog: "bark",
  cat: "meow",
  pig: "oink",
};

function animalsAndSounds(animals, animal) {
  return animals[animal];
}

const result = animalSounds(animals, "cat");
console.log(result); // Output will be 'meow'

Regardless of the number of key-value pairs in the object (animals), accessing an element by key using bracket notation obj[key] takes the same amount of time.

2. O(log n) - Logarithmic

The algorithm's runtime or space usage grows logarithmically with the size of the input. Commonly seen in binary search algorithms.

// Binary search function to find an element in a sorted array
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    // Find the middle element
    const mid = Math.floor((left + right) / 2);

    // If the middle element is the target, return its index
    if (arr[mid] === target) {
      return mid;
    }

    // If the target is less than the middle element, search the left half
    if (arr[mid] > target) {
      right = mid - 1;
    } // If the target is greater than the middle element, search the right half
    else {
      left = mid + 1;
    }
  }

  // If the target is not found, return -1
  return -1;
}

// Example usage
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const targetElement = 13;
const index = binarySearch(sortedArray, targetElement);
console.log("Index of", targetElement, ":", index); // Output will be: Index of 13 : 6

The binary search algorithm works by repeatedly dividing the search interval in half until the target element is found, the time complexity of binary search is O(log n), where n is the number of elements in the array.

3. O(n) - Linear

The algorithm's runtime or space usage grows linearly with the size of the input. Each additional input element adds a constant amount of time or space.

// Function to find the maximum element in an array
function findMax(arr) {
  // Initialize max variable to store the maximum value
  let max = arr[0]; // Assume the first element is the maximum

  // Iterate through the array to find the maximum element
  for (let i = 1; i < arr.length; i++) {
    // Update max if the current element is greater
    if (arr[i] > max) {
      max = arr[i];
    }
  }

  // Return the maximum element found
  return max;
}

// Example usage
const array = [3, 7, 1, 9, 5, 2, 8, 4, 6];
const maxElement = findMax(array);
console.log("Maximum element:", maxElement); // Output will be: Maximum element: 9

4. O(n log n) - Linearithmic

The algorithm's runtime or space usage grows in proportion to n times the logarithm of n. Commonly seen in efficient sorting algorithms like quicksort.

// Merge function to merge two sorted arrays
function merge(leftArr, rightArr) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // Merge left and right arrays into result array in sorted order
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      result.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }

  // Concatenate remaining elements of left and right arrays
  return result.concat(leftArr.slice(leftIndex), rightArr.slice(rightIndex));
}

// Merge sort function
function mergeSort(arr) {
  // Base case: If the array has 0 or 1 element, it is already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Split the array into two halves
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  // Recursively sort the two halves
  const sortedLeft = mergeSort(leftArr);
  const sortedRight = mergeSort(rightArr);

  // Merge the sorted halves
  return merge(sortedLeft, sortedRight);
}

// Example usage
const unsortedArray = [3, 7, 1, 9, 5, 2, 8, 4, 6];
const sortedArray = mergeSort(unsortedArray);
console.log("Sorted array:", sortedArray);

5. O(n^2) Quadratic

The algorithm's runtime or space usage grows quadratically with the size of the input. Commonly seen in algorithms with nested loops over the input.

// Bubble sort function
function bubbleSort(arr) {
  const n = arr.length;

  // Iterate through the array elements
  for (let i = 0; i < n; i++) {
    // Last i elements are already in place, so we only need to check the first n-i elements
    for (let j = 0; j < n - i - 1; j++) {
      // Swap adjacent elements if they are in the wrong order
      if (arr[j] > arr[j + 1]) {
        // Swap arr[j] and arr[j + 1]
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [3, 7, 1, 9, 5, 2, 8, 4, 6];
const sortedArray = bubbleSort(unsortedArray);
console.log("Sorted array:", sortedArray);

6. O(n^k) - Polynomial

The algorithm's runtime or space usage grows as a polynomial function of the input size, where k is a constant exponent.

// Function to find the sum of all triplets of elements in an array
function findSumOfTriplets(arr) {
  const n = arr.length;
  let sum = 0;

  // Nested loops to iterate over all triplets of elements in the array
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        sum += arr[i] + arr[j] + arr[k];
      }
    }
  }

  return sum;
}

// Example usage
const array = [1, 2, 3, 4, 5];
const sum = findSumOfTriplets(array);
console.log("Sum of all triplets:", sum);

7. O(2^n) - Exponential

The algorithm's runtime or space usage grows exponentially with the size of the input. Commonly seen in brute-force algorithms that explore all possible solutions.

// Function to generate all subsets of a set using recursion
function generateSubsets(set) {
  // Base case: If the set is empty, return an array containing an empty set
  if (set.length === 0) {
    return [[]];
  }

  // Remove the first element from the set
  const firstElement = set[0];
  const remainingSet = set.slice(1);

  // Recursively generate subsets without the first element
  const subsetsWithoutFirst = generateSubsets(remainingSet);

  // Generate subsets including the first element by adding it to each subset
  const subsetsWithFirst = subsetsWithoutFirst.map(
    (subset) => [firstElement, ...subset],
  );

  // Concatenate subsets without and with the first element
  return subsetsWithoutFirst.concat(subsetsWithFirst);
}

// Example usage
const set = [1, 2, 3];
const subsets = generateSubsets(set);
console.log("All subsets:", subsets);

8. O(n!) - Factorial

The algorithm's runtime or space usage grows factorialy with the size of the input. Commonly seen in algorithms that generate all permutations or combinations of a set.

// Function to generate all permutations of a set using recursion
function generatePermutations(set) {
  const permutations = [];

  // Base case: If the set is empty, return an array containing an empty permutation
  if (set.length === 0) {
    return [[]];
  }

  // Iterate through each element in the set
  for (let i = 0; i < set.length; i++) {
    // Create a copy of the set without the current element
    const remainingSet = set.slice(0, i).concat(set.slice(i + 1));

    // Recursively generate permutations of the remaining set
    const subPermutations = generatePermutations(remainingSet);

    // Append the current element to each permutation of the remaining set
    for (const subPermutation of subPermutations) {
      permutations.push([set[i], ...subPermutation]);
    }
  }

  return permutations;
}

// Example usage
const set = [1, 2, 3];
const permutations = generatePermutations(set);
console.log("All permutations:", permutations);

Conclusion

Analyzing algorithm complexity helps in:

A handy table wrapping everything up:

Big O notation Name Sample
O(1) Constant Dictionary or object access
O(log 1) Logarithmic Binary search
O(n) Linear Loop
O(n log n) Linerithmic Loop * binary search
O(n^2) Quadratic Two nested loops
O(n^k) Polinomial k nested loops
O(2^n) Exponential Recursion
O(n!) Factorial Recursion within a loop