Start learning free

KOTLIN · BIG O NOTATION

Time Complexity Practice 3 in Kotlin, explained

What quadratic time means

An algorithm runs in quadratic time, written O(n²), when the work grows with the square of the input size. Double the input and the work becomes four times as large; make it ten times larger and the work grows a hundredfold. For small inputs that is fine. For large ones it quickly becomes too slow.

The usual sign of quadratic time is a loop inside a loop, where both loops run over the input.

The classic example: nested loops

This function counts how many pairs of numbers in an array add up to 10:

fun countPairs(nums: IntArray): Int {
    var count = 0
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] + nums[j] == 10) count++
        }
    }
    return count
}

Calling it with intArrayOf(1, 9, 5, 5, 3, 7) returns 3, for the pairs 1 and 9, 5 and 5, and 3 and 7.

The outer loop runs n times. For each value of i, the inner loop checks the elements after it: n - 1 of them, then n - 2, and so on down to 0. The total number of comparisons is

(n - 1) + (n - 2) + ... + 1 + 0 = n * (n - 1) / 2

That is n²/2 - n/2. Big O drops constant factors and lower-order terms, so n²/2 - n/2 becomes O(n²). The inner loop does not start at 0, and the work is still quadratic.

Counting iterations directly

When both loops run the full range, the count is exactly n * n:

var steps = 0
val n = 6
for (i in 0 until n) for (j in 0 until n) steps++
println(steps)  // 36

With n = 6 the program prints 36. With n = 4 the same pattern gives 16.

Loops that are not quadratic

Two loops do not always mean O(n²). Look at what each loop runs over:

  • Loops one after another add up. A loop of n iterations followed by another loop of n iterations is n + n = 2n, which is O(n).
  • Nested loops with a fixed inner range are not quadratic. If the inner loop always runs 3 times, the total is 3n, so O(n).
  • Nested loops over different inputs multiply as separate sizes. An outer loop over a list of length a and an inner loop over a list of length b is O(a * b). It is quadratic only when both lengths are about n.
  • A hidden loop counts. A single loop whose body calls something that copies or searches n elements is also quadratic. Joining strings with += inside a loop, or calling list.contains(x) for each element, are the common cases.

Here is the hidden-loop case. List.contains scans the list from the start, so it costs O(n):

fun hasDuplicate(nums: List<Int>): Boolean {
    for (i in nums.indices) {
        if (nums.indexOf(nums[i]) != i) return true
    }
    return false
}

The loop looks single, but indexOf scans up to n elements on each pass, so the function is O(n²). Putting the values in a HashSet brings it down to O(n), because checking a set takes O(1) on average.

Why it matters

Here is how the number of steps grows. A computer does very roughly a hundred million simple steps per second, so the last rows show where quadratic code starts to hurt:

nn (linear)n² (quadratic)
10010010,000
10,00010,000100,000,000
1,000,0001,000,0001,000,000,000,000

An O(n²) solution is fine for an input of a few thousand elements and unusable for a million. When a problem states large limits, a quadratic approach is usually the brute force that a better idea replaces, with sorting, a hash set or two pointers.

Common mistakes when analysing loops

  • Counting loops instead of iterations. Two nested loops can be O(n) when the inner one has a fixed size, and one loop can be O(n²) when its body copies the input.
  • Keeping the constant. The pair loop above does about n²/2 comparisons, but its complexity is written O(n²), not O(n²/2).
  • Forgetting that the inner range depends on i. A triangular loop like j in i + 1 until n is still quadratic because the sum n * (n - 1) / 2 grows like n².
  • Mixing up the sizes. If the loops run over two different inputs, name the sizes separately instead of calling both n.

Key takeaways

  • Quadratic time, O(n²), means the work grows with the square of the input size. Doubling the input quadruples the work.
  • Two nested loops that each run over the input give n * n iterations. A triangular pair of loops gives n * (n - 1) / 2, which is still O(n²).
  • Look for hidden loops in calls such as indexOf, contains, substring and += on strings.
  • For large inputs, replace a quadratic approach with a faster one when the problem allows it.
Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free