Go Quadratic Time O(n²)

A Loop Inside a Loop

O(n²) means quadratic time: the work grows with the square of the input. Twice the elements, four times the steps. Ten times the elements, a hundred times the steps.

The tell-tale shape in code is a loop inside a loop, both running over the same data. The outer loop runs n times, and for each of those the inner loop runs n times again: n · n steps.

Quadratic is fine for small slices. For 100,000 elements it is already 10 billion steps — that is where programs start to hang.

All Pairs

The most direct O(n²) task: combine every element with every element. 4 letters make 4 · 4 = 16 pairs; 100 letters would make 10,000.

Build every pair

The outer loop picks x, the inner loop pairs it with every y. 4 elements produce 16 pairs — the square of the input size.

Write a Go program with the slice a, b, c, d that uses two nested loops to print every pair of letters (like aa ab ac ad) on one line per outer element, counting the pairs. At the end print how many elements made how many pairs.

> Output: Go program and captured output

Prompt

Write a Go program with the slice a, b, c, d that uses two nested loops to print every pair of letters (like aa ab ac ad) on one line per outer element, counting the pairs. At the end print how many elements made how many pairs.

Output: Go program and captured output

package main

import "fmt"

func main() {
  letters := []string{"a", "b", "c", "d"}
  pairs := 0

  for _, x := range letters {
    for _, y := range letters {
      fmt.Print(x+y, " ")
      pairs++
    }
    fmt.Println()
  }

  fmt.Println(len(letters), "elements made", pairs, "pairs")
}

Bubble Sort

Bubble sort is the classic quadratic algorithm: it repeatedly walks the slice and swaps neighbours that are in the wrong order. Big values "bubble" to the end, one pass at a time.

With its two nested loops it makes about n²/2 comparisons. It is a great algorithm to learn from — and a bad one to use: slices.Sort() does the same job in O(n log n).

Sort with two nested loops

Sorting 5 elements takes 4 + 3 + 2 + 1 = 10 comparisons. For 1,000 elements it would be about half a million — while an O(n log n) sort needs about ten thousand.

Write a Go program that sorts the slice 5, 3, 8, 1, 4 with bubble sort — two nested loops that swap neighbours in the wrong order — while counting the comparisons. Print the sorted slice and the number of comparisons.

> Output: Go program and captured output

Prompt

Write a Go program that sorts the slice 5, 3, 8, 1, 4 with bubble sort — two nested loops that swap neighbours in the wrong order — while counting the comparisons. Print the sorted slice and the number of comparisons.

Output: Go program and captured output

package main

import "fmt"

func main() {
  nums := []int{5, 3, 8, 1, 4}
  comparisons := 0

  for i := 0; i < len(nums)-1; i++ {
    for j := 0; j < len(nums)-1-i; j++ {
      comparisons++
      if nums[j] > nums[j+1] {
        nums[j], nums[j+1] = nums[j+1], nums[j]
      }
    }
  }

  fmt.Println("sorted:", nums)
  fmt.Println("comparisons:", comparisons)
}

Duplicates the Slow Way

Checking every element against every element that comes after it is another nested-loop pattern — comparing all pairs to find a duplicate.

It works, but it is O(n²). The Space Complexity page in this group shows the standard trick that makes this linear: remember the values you have already seen in a map.

Find a duplicate with two loops

Each element is compared with every later element. The duplicate pair of 1s is found after 7 checks; in the worst case — no duplicate at all — all 15 pair checks run.

Write a Go program that finds a duplicate value in the slice 3, 1, 4, 1, 5, 9 by comparing every element with every later element in two nested loops, counting the checks. When a duplicate is found, print the value and the number of checks so far.

> Output: Go program and captured output

Prompt

Write a Go program that finds a duplicate value in the slice 3, 1, 4, 1, 5, 9 by comparing every element with every later element in two nested loops, counting the checks. When a duplicate is found, print the value and the number of checks so far.

Output: Go program and captured output

package main

import "fmt"

func main() {
  nums := []int{3, 1, 4, 1, 5, 9}
  checks := 0

  for i := 0; i < len(nums); i++ {
    for j := i + 1; j < len(nums); j++ {
      checks++
      if nums[i] == nums[j] {
        fmt.Println("duplicate:", nums[i], "after", checks, "checks")
      }
    }
  }
}