Hands-On Data Structures and Algorithms with JavaScript

Quadratic time

With quadratic time algorithms, we have now entered the dark side of the time complexity. As the name suggests, the size of the input quadratically affects the running time of the algorithm. One common example is nested loops:

for (int i = 0; i <n; i += c) {
    for (int j = 0; j < n; j += c) {
        // some O(1) expressions
    }
}

As you can see from the preceding example, for i = 0, the inner loop runs n times, and the same for i = 1, and i = 2, and so on. The inner loop always runs n times and is not dependent on the value of n, thus making the algorithms time complexity O(n²).