Big O O N 2

O(n^2) - Quadratic Time Complexity

Introduction to O(n^2)

O(n^2), or Quadratic Time complexity, is a common complexity class where the time taken by an algorithm increases quadratically as the input size grows. It is typically seen in algorithms that involve nested iterations over the data set.

Explanation of O(n^2)

In an O(n^2) algorithm, operations are usually composed of two nested loops, each iterating through the input data. As a result, for every element in the input, the algorithm performs a number of operations proportional to the size of the input, leading to a quadratic increase in the total number of operations.

Assessment of O(n^2)

Quadratic time complexity is less efficient than linear time complexity, especially as the size of the input grows large. It can be suitable for small to medium-sized data sets but becomes increasingly inefficient with larger data. Identifying and optimizing O(n^2) algorithms is often a key area of focus for performance improvement.

JavaScript Code Examples

Example 1: Bubble Sort Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It’s a classic example of O(n^2) complexity.

	function bubbleSort(arr) {
	  for (let i = 0; i < arr.length; i++) {
	    for (let j = 0; j < arr.length - i - 1; j++) {
	      if (arr[j] > arr[j + 1]) {
	        let temp = arr[j];
	        arr[j] = arr[j + 1];
	        arr[j + 1] = temp;
	      }
	    }
	  }
	  return arr;
	}

Calculation of Time Complexity for Bubble Sort:

1. For each element in the array (n), the inner loop performs n iterations, decreasing by 1 each time.
2. This results in a total of approximately n * (n/2) operations, which simplifies to O(n^2).

Example 2: Checking All Pairs in an Array Comparing all possible pairs in an array to check for a condition is another common scenario for O(n^2) complexity.

	function findAllPairs(arr) {
	  let pairs = [];
	  for (let i = 0; i < arr.length; i++) {
	    for (let j = i + 1; j < arr.length; j++) {
	      pairs.push([arr[i], arr[j]]);
	    }
	  }
	  return pairs;
	}

Calculation of Time Complexity for Finding All Pairs:

1. The first loop iterates n times, and for each iteration, the second loop iterates n - 1 times on average.
2. This results in approximately n * (n - 1) / 2 total iterations, which is O(n^2).

These examples highlight O(n^2) complexity, where operations increase quadratically with the input data size. Upcoming sections will delve into even more complex time complexities, providing insights and JavaScript implementations for each.