DEV Community

Trinmar Boado
Trinmar Boado

Posted on

Big-O Notation

Sure! Big O notation is used to describe the time complexity of algorithms. In JavaScript, various algorithms may exhibit different time complexities. Here are some examples with explanations:

  1. Constant Time O(1):
function constantTimeExample(arr) {
    return arr[0]; // Accessing the first element in the array, regardless of the array size, takes constant time.
}
Enter fullscreen mode Exit fullscreen mode
  1. Linear Time O(n):
function linearTimeExample(arr) {
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i]); // The function loops through the entire array, and the running time grows linearly with the array size.
    }
}
Enter fullscreen mode Exit fullscreen mode
  1. Quadratic Time O(n^2):
function quadraticTimeExample(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]); // Nested loops make the function run n^2 times, where n is the array size.
        }
    }
}
Enter fullscreen mode Exit fullscreen mode
  1. Logarithmic Time O(log n):
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}
// In a binary search, the search space is divided in half at each step, making it logarithmic time complexity.
Enter fullscreen mode Exit fullscreen mode
  1. Polynomial Time O(n^k):
function polynomialTimeExample(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            for (let k = 0; k < arr.length; k++) {
                console.log(arr[i], arr[j], arr[k]); // Triple nested loop makes the function run n^3 times, where n is the array size.
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

These examples demonstrate how Big O notation helps us understand how the performance of an algorithm changes as the size of the input data increases. It allows us to analyze and compare different algorithms to choose the most efficient one for a particular problem.

Time Complexity and Space Complexity are two fundamental concepts in computer science that help analyze the efficiency and resource usage of algorithms and data structures. Let's delve into these concepts with JavaScript examples:

1. Time Complexity:
Time complexity measures how the running time of an algorithm or function scales with the input size. It provides an estimate of the number of basic operations (e.g., comparisons, assignments) an algorithm requires to complete its task, as a function of the input size. Common time complexities are denoted using Big O notation (e.g., O(1), O(n), O(n^2)).

Examples:

  • Constant Time O(1):
  function constantTimeExample(arr) {
      return arr[0]; // Regardless of the array size, accessing the first element takes constant time.
  }
Enter fullscreen mode Exit fullscreen mode
  • Linear Time O(n):
  function linearTimeExample(arr) {
      for (let i = 0; i < arr.length; i++) {
          console.log(arr[i]); // The function loops through the entire array, taking time proportional to 'n', the array size.
      }
  }
Enter fullscreen mode Exit fullscreen mode
  • Quadratic Time O(n^2):
  function quadraticTimeExample(arr) {
      for (let i = 0; i < arr.length; i++) {
          for (let j = 0; j < arr.length; j++) {
              console.log(arr[i], arr[j]); // Double nested loop makes the function run 'n' times for each 'n' element, resulting in 'n^2' time complexity.
          }
      }
  }
Enter fullscreen mode Exit fullscreen mode

2. Space Complexity:
Space complexity measures the amount of memory an algorithm uses with respect to the input size. It's concerned with the growth of memory usage as the input size increases. Similar to time complexity, space complexity is also represented using Big O notation.

Examples:

  • Constant Space O(1):
  function constantSpaceExample(n) {
      let result = 0;
      for (let i = 0; i < n; i++) {
          result += i; // The 'result' variable consumes a fixed amount of memory, regardless of 'n'.
      }
      return result;
  }
Enter fullscreen mode Exit fullscreen mode
  • Linear Space O(n):
  function linearSpaceExample(n) {
      let arr = [];
      for (let i = 0; i < n; i++) {
          arr.push(i); // The 'arr' array grows linearly with 'n', leading to linear space complexity.
      }
      return arr;
  }
Enter fullscreen mode Exit fullscreen mode
  • Quadratic Space O(n^2):
  function quadraticSpaceExample(n) {
      let matrix = [];
      for (let i = 0; i < n; i++) {
          matrix.push(Array(n).fill(0)); // Creating a 2D matrix with 'n' rows and 'n' columns leads to quadratic space complexity.
      }
      return matrix;
  }
Enter fullscreen mode Exit fullscreen mode

Understanding time and space complexity is crucial for designing efficient algorithms and data structures, as it helps in making informed choices about which algorithm to use for a given problem and how it will perform as the input size grows.

Top comments (0)