Discovering JavaScript's Hidden Secrets: Understanding Big O Notation in Data Structures & Algorithms.

Welcome to the world of Data Structures and Algorithms using JavaScript! This comprehensive guide is designed to equip you with the essential knowledge and skills necessary to navigate the complex landscape of data manipulation and algorithmic problem-solving with JavaScript.

Whether you're a seasoned developer looking to enhance your proficiency or a beginner eager to explore the realms of data structures and algorithms, this content is tailored to provide clarity and practical insights. Join us on a journey that combines theoretical foundations with hands-on coding examples, empowering you to write robust and efficient solutions in JavaScript.

Prerequisites

To effectively engage with data structures and algorithms using JavaScript, it is important to have a strong understanding of JavaScript fundamentals. This includes proficiency in basic syntax, variables, data types, control flow structures, functions, and scope.

This lesson will cover data structures and algorithms in series. In this first episode, we'll dive into Big O notation's fundamentals, a crucial concept for understanding algorithmic efficiency and performance analysis.

Big O notation

Big O notation is a powerful tool for analyzing and articulating the efficiency or complexity of an algorithm. Notably, it provides insights into both time and space complexities. When addressing time complexity, Big O is represented as O(f(n)), where 'O' signifies the 'order of,' denoting the upper bound or worst-case scenario for the algorithm's growth rate. The 'f' corresponds to a function, much like those in mathematics, while 'n' signifies the size of inputs the function processes. This 'n' typically represents the number of elements in data structures like arrays, the length of strings, the number of nodes in a graph, or any other relevant metric related to the input size. Consequently, 'f(n)' becomes a function representing the algorithm's time complexity growth rate in relation to the input size 'n'. Similarly, Big O notation for space complexity adopts the form O(g(n)), where 'g' represents another function, reflecting the upper bound of the algorithm's space usage as it scales with the input size 'n'. Like time complexity, space complexity analysis aims to provide an understanding of how the algorithm's memory consumption grows with increasing input size.

In JavaScript, the execution time of an algorithm can be accurately measured using the performance.now() method. This allows developers to compare the efficiency of different algorithmic solutions or implementations for the same problem. By timing the execution of each function and analyzing the differences in performance, valuable insights can be gained into the efficiency levels of the respective algorithms. In the example below, we'll compare two functions that solve the same problem, showcasing the difference in their efficiency levels.

// 1st approach: which is less efficient
function findDivisor1(number) {
  const startime = performance.now();
  const arrayOfDivisor = [];
  for (let i = 1; i <= number; i++) {
    if (number % i === 0) {
      arrayOfDivisor.push(i);
    }
  }
  const endtime = performance.now();
  const elapsedTime = endtime - startime;
  console.log("Elapsed Time for 1st approach:", elapsedTime);
  return arrayOfDivisor;
}
// Example usage:
console.log("findDivisor1", findDivisor1(10000000));
// result: Elapsed Time for 1st approach: 56.06390005350113

// 2nd approach: which is more efficient
function findDivisor2(number) {
  const startime = performance.now();
  const arrayOfDivisor = [];
  for (let i = 1; i <= Math.sqrt(number); i++) {
    if (number % i === 0) {
      arrayOfDivisor.push(i);
      // If the divisor is not equal to the square root, add its pair
      if (i !== Math.sqrt(number)) {
        arrayOfDivisor.push(number / i);
      }
    }
  }
  //   sorts the array in ascending order
  const sortedArrayOfDivisor = arrayOfDivisor.sort((a, b) => a - b);
  const endtime = performance.now();
  const elapsedTime = endtime - startime;
  console.log("Elapsed Time for 2nd approach:", elapsedTime);
  return sortedArrayOfDivisor;
}
// Example usage:
console.log("findDivisor2", findDivisor2(10000000));
// result: Elapsed Time for 2nd approach: 0.35019999742507935

The difference between the efficiency in those examples written above leads us to discuss the analysis of Big O notation for algorithm complexity.

Big O notation for algorithm complexity analysis:

• O(1) Constant complexity: Constant complexity, denoted as O(1), signifies an algorithm's efficiency where the execution time and space remain constant regardless of input size. This implies that the algorithm's performance does not depend on the size of the input data. A classic example demonstrating constant complexity is accessing an element in an array by its index as shown below.

// function for retrieving an item from an array by index
function accessElementByIndex(arr, index) {
  if (
    !isNaN(index) &&
    Number.isInteger(index) &&
    index >= 0 &&
    index < arr.length
  ) {
    return arr[index];
  } else {
    return "Index is out of bounds";
  }
}
// Example usage:
const arrayOfNumbers = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(accessElementByIndex(arrayOfNumbers, 2));
//result: 3

• O(log n) Logarithmic complexity: Logarithmic complexity, denoted as O(log n), characterizes algorithms whose execution time or space usage grows logarithmically with the size of the input data. In other words, as the input size increases, the time or space required increases at a logarithmic rate. For example, binary search algorithms exhibit logarithmic complexity, as they halve the search space with each step, resulting in a time complexity proportional to the logarithm of the input size. An example of a logarithmic complexity is shown below.

// A binary search function for finding the index of a target element in a sorted array.
function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // Target not found
}

// Example usage:
const arrayOfNumbers = [1, 2, 3, 4, 5, 6, 7];
console.log(binarySearch(arrayOfNumbers, 5));
//   result: 4

• O(n) Linear complexity: Linear complexity, denoted as O(n), represents algorithms whose execution time and space usage increase linearly with the size of the input data. In simpler terms, as the input size grows, the time and space required by the algorithm also grow proportionally. An example illustrating linear complexity is presented below.

// A function for finding the maximum element in an array
function findMaxElement(arr) {
  let max = arr[0];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }

  return max; // Return the maximum element in the array
}

// Example usage:
const arrayOfNumbers = [5, 2, 8, 1, 9, 4];
console.log(findMaxElement(arrayOfNumbers));
// result: 9

• O(n^2) Quadratic complexity: Quadratic complexity, denoted as O(n^2), characterizes algorithms whose execution time and space requirements increase quadratically with the size of the input data. Put simply, as the input size grows, the time and space needed to complete the algorithm increase proportionally to the square of the input size. An example demonstrating quadratic complexity is provided below.

// A bubble sort function for sorting numbers in an array
function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap them if they are in the wrong order
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

// Example usage:
const unsortedArrayOfNumbers = [64, 25, 12, 22, 11];
console.log(bubbleSort(unsortedArrayOfNumbers));
// result: [ 11, 12, 22, 25, 64 ]

• O(n^3) Cubic complexity: Cubic complexity, denoted as O(n^3), is a measure of algorithmic efficiency where the execution time and space of an algorithm grows cubically with the size of the input data. In simpler terms, as the input size increases, the time and space required to complete the algorithm increases proportionally to the cube of the input size. An example illustrating cubic time complexity is provided below.

// Function to calculate the sum of all elements in a 3D matrix
function sumOfMatrix(matrix) {
  const n = matrix.length;
  let totalSum = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // Accumulate the sum of all elements
        totalSum += matrix[i][j][k];
      }
    }
  }

  return totalSum;
}

// Example usage:
const threeDMatrix = [
  [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
  ],
  [
    [10, 11, 12],
    [13, 14, 15],
    [16, 17, 18],
  ],
  [
    [19, 20, 21],
    [22, 23, 24],
    [25, 26, 27],
  ],
];

console.log(sumOfMatrix(threeDMatrix));
// result: 378

• O(2^n) Exponential complexity: Exponential complexity, denoted as O(2^n) or sometimes O(k^n), is a measure of algorithmic efficiency where the execution time and space of an algorithm grows exponentially with the size of the input data. In simple terms, as the input size increases, the time and space required to complete the algorithm increases exponentially, typically doubling with each additional element in the input. An example demonstrating exponential time complexity is provided below.

// A Fibonacci function to calculate the nth Fibonacci number recursively
function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

// Example usage:
console.log(fibonacci(7));
// result: 13

Algorithm analysis aims to understand the efficiency of algorithms, predicting their performance as input sizes grow. This involves calculating both time (f(n)) and space (g(n)) complexities. However, it can be a little bit challenging to calculate. Big-O notation provides some fundamental ways to simplify any algorithm to help developers calculate.

Simplifying Big O expressions

• O(2n) simplifies to O(n)
• O(500) simplifies to O(1)
• O(13n^2) simplifies to O(n^2)
• O(n+10) simplifies to O(n)
• O(1000n+50) simplifies to O(n)
• O(n^2+5n+8) simplifies to O(n^2)

Little tricks to take note in Big O notation

Time complexity

• Arithmetic operations, variable assignments, and accessing elements in arrays or objects are typically constant time.
• In loops, the complexity depends on the number of iterations multiplied by the complexity of operations within the loop.

Space complexity

• Most primitive data types have constant space complexity.
• Strings require O(n) space, where n is the length of the string.
• Reference types like arrays or objects generally have O(n) space complexity, where n is the number of elements or keys.

It's important to note that while these rules provide general guidelines, analyzing algorithm complexity can sometimes be more complex depending on specific contexts and implementations.

Conclusion

This series has provided a comprehensive exploration of Big O notation. Understanding the efficiency of algorithms is crucial for making informed decisions in software development. By unraveling the complexities of Big O notation, we've gained valuable insights into how algorithms scale and perform under different input sizes. Moving forward, applying this knowledge will undoubtedly contribute to the enhancement of software performance and the optimization of computational resources in real-world applications.

Resources and References

You can check out some of the resources listed below to learn more about Big O notation

• JavaScript Data Structures and Algorithms by Sammie Bae
• js algorithms and data structures masterclass by Colt Steele