What quadratic time means
An algorithm runs in quadratic time, written O(n²), when doubling the input makes it about four times slower. It usually comes from doing O(n) work once for each of the n elements. With 1,000 elements that is around a million basic steps, and with 100,000 elements it is ten billion.
Nested loops
The most common source is a loop inside a loop where both run up to n:
def printGrid(n: Int): Unit = {
for (i <- 0 until n; j <- 0 until n) print(s"($i,$j) ")
println()
}
In Scala, for (i <- 0 until n; j <- 0 until n) is a nested loop written on one line: for each i, the inner loop runs through every j. With n = 3 the output is:
(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)
The body runs n * n times, so the function is O(n²). The same is true if you write two separate for loops, one inside the other, as in for (i <- 1 to 10) for (j <- 1 to 10) ..., which runs its body 100 times.
When the inner loop depends on the outer one
The inner loop does not have to run all n times. A common shape starts the inner loop just after the outer index, to look at every pair of elements once:
def countPairs(a: Array[Int]): Int = {
var count = 0
for (i <- a.indices; j <- i + 1 until a.length) count += 1
count
}
The inner loop runs n - 1 times for i = 0, then n - 2, and so on down to 0. The total is (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2. The results match the formula:
countPairs of 10 elements = 45
countPairs of 100 elements = 4950
countPairs of 1000 elements = 499500
That is half of n² minus half of n. Big O drops constant factors and lower-order terms, so n(n - 1) / 2 is still O(n²). Checking every pair for a duplicate is the usual example:
def hasDuplicate(a: Array[Int]): Boolean = {
var i = 0
while (i < a.length) {
var j = i + 1
while (j < a.length) {
if (a(i) == a(j)) return true
j += 1
}
i += 1
}
false
}
hasDuplicate(Array(4, 1, 7, 1)) returns true and hasDuplicate(Array(4, 1, 7)) returns false. The worst case, when there is no duplicate, compares every pair, so the time is O(n²) and the extra space is O(1).
Hidden quadratic loops
A quadratic algorithm does not always show two loops. If the body of a loop calls a method that itself walks the collection, the costs multiply:
for (x <- arr) {
if (arr.contains(x)) { /* ... */ } // contains is O(n), inside an O(n) loop
}
The same happens with indexOf, count and filter used inside a loop, with list(i) on a List (which costs O(i)), and with building a string by repeated +. When you analyze a function, count the cost of every call in the loop body, not just the loops you can see.
Not every nested loop is quadratic
- Different sizes. A loop over
nitems nested in a loop overmitems isO(n * m). It is quadratic only when both are about the same size. - Loops one after another. Two sequential loops over
nitems costO(n + n) = O(n). - A fixed inner loop. An inner loop that always runs 3 times adds a constant factor, so the whole function stays
O(n). - Halving inner loops. If the inner loop halves its range each time, as in binary search, the total is
O(n log n).
Reducing quadratic work
Many quadratic algorithms can be made faster by trading memory for time. A duplicate check can use a scala.collection.mutable.HashSet to remember what was seen, and test each element in O(1) on average, giving O(n) time and O(n) space. Sorting first and comparing neighbours gives O(n log n) time.
Common mistakes
- Counting only the visible loops. Methods such as
containsandindexOfare loops too. - Keeping the constant.
n(n - 1) / 2is writtenO(n²), notO(n² / 2). - Assuming small inputs predict large ones. A quadratic function that feels instant at 100 elements needs roughly a hundred times more steps at 1,000.
Key takeaways
- Quadratic time means about
n * nsteps; doubling the input quadruples the work. - A nested loop in which both loops run up to about
nisO(n²), including the pairs pattern withn(n - 1) / 2steps. - A linear method called inside a linear loop is also quadratic.
- Look for a set, a map or a sort to bring the cost down.
