O(n^2) - Quadratic Time Complexity
Description: Quadratic time complexity, denoted as O(n^2), occurs when the time it takes to complete an operation is proportional to the square of the input size. This often happens in algorithms that involve nested loops, where each loop iterates over the entire input.
Example: Nested Loops
Consider the following JavaScript function:
Explanation
In this example, the printAllPairs function takes an array as input and prints out all possible pairs of elements in the array.
-
Nested Loops: The function uses two nested loops. The outer loop (with variable i) iterates over each element in the array. For each iteration of i, the inner loop (with variable j) iterates over the entire array again.
-
Operations Count: For each value of i, the inner loop j runs from 0 to the size of the array n. This means that for each iteration of i, the inner loop will perform n operations. Therefore, the total number of operations for the function is i * n.
-
Quadratic Growth: Since i also iterates from 0 to n, the total number of operations is proportional to n * n, which is n^2. This is why the time complexity is O(n^2).
Visualizing Quadratic Time Complexity:
Let’s break down the operations for an array of size n:
-
When i = 0, the inner loop runs n times.
-
When i = 1, the inner loop runs n times.
-
This pattern continues until i = n-1.
-
In total, the function performs approximately n * n operations, resulting in O(n^2) complexity.
Why Is This Important?
Fig:- In above figure, you can see for each value of n, no of operations required to solve that problem is quadratic.
Note - Quadratic time complexity can become a performance bottleneck for large datasets. As the size of the input grows, the time required to complete the operation increases exponentially. For small input sizes, O(n^2) algorithms may run efficiently, but as n increases, they become significantly slower compared to algorithms with lower time complexities, like O(n) or O(log n).
