Big-O: measuring algorithms

total := 0
for _, x := range nums { // runs n times
	total += x            // 1 step each
}

for i := range nums {         // n times
	for j := range nums {     // n times for each i
		if nums[i]+nums[j] == 0 { ... }
	}
}

package main
 
import "fmt"
 
func linear(n int) int {
	steps := 0
	for i := 0; i < n; i++ {
		steps++
	}
	return steps
}
 
func quadratic(n int) int {
	steps := 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			steps++
		}
	}
	return steps
}
 
func logarithmic(n int) int {
	steps := 0
	for n > 1 {
		n /= 2 // halve the problem
		steps++
	}
	return steps
}
 
func main() {
	fmt.Printf("%7s %7s %10s %9s\n", "n", "O(n)", "O(n²)", "O(log n)")
	for _, n := range []int{10, 100, 1000, 10000} {
		fmt.Printf("%7d %7d %10d %9d\n", n, linear(n), quadratic(n), logarithmic(n))
	}
}

      n    O(n)      O(n²)  O(log n)
     10      10        100         3
    100     100      10000         6
   1000    1000    1000000         9
  10000   10000  100000000        13

package main
 
import (
	"fmt"
	"math/rand"
	"slices"
	"time"
)
 
// O(n²) time, O(1) space
func hasDupPairs(nums []int) bool {
	for i := range nums {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] == nums[j] {
				return true
			}
		}
	}
	return false
}
 
// O(n log n) time; sorts a copy so the caller's slice is untouched
func hasDupSort(nums []int) bool {
	s := slices.Clone(nums)
	slices.Sort(s)
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			return true
		}
	}
	return false
}
 
// O(n) time, O(n) space
func hasDupSet(nums []int) bool {
	seen := make(map[int]struct{}, len(nums))
	for _, n := range nums {
		if _, ok := seen[n]; ok {
			return true
		}
		seen[n] = struct{}{}
	}
	return false
}
 
func main() {
	fmt.Println(hasDupPairs([]int{1, 2, 3, 1}), hasDupSort([]int{1, 2, 3}), hasDupSet([]int{4, 4}))
 
	nums := rand.Perm(20_000) // no duplicates: the worst case for all three
	timeIt := func(fn func([]int) bool) time.Duration {
		start := time.Now()
		fn(nums)
		return time.Since(start)
	}
	pairs, sorted, set := timeIt(hasDupPairs), timeIt(hasDupSort), timeIt(hasDupSet)
	fmt.Println("pairs at least 10x slower than sort:", pairs > 10*sorted)
	fmt.Println("pairs at least 10x slower than set: ", pairs > 10*set)
}

true false true
pairs at least 10x slower than sort: true
pairs at least 10x slower than set:  true

package main
 
import "fmt"
 
// Looks like one loop over a, but scans b for every x: O(len(a) × len(b)).
func commonScan(a, b []int) (out []int, work int) {
	for _, x := range a {
		for _, y := range b { // what slices.Contains(b, x) does inside
			work++
			if x == y {
				out = append(out, x)
				break
			}
		}
	}
	return out, work
}
 
// Pays O(len(b)) once to build a set, then O(1) per lookup: O(len(a) + len(b)).
func commonSet(a, b []int) (out []int, work int) {
	set := make(map[int]bool, len(b))
	for _, y := range b {
		set[y] = true
		work++
	}
	for _, x := range a {
		work++
		if set[x] {
			out = append(out, x)
		}
	}
	return out, work
}
 
func main() {
	a := make([]int, 1000) // 0..999
	b := make([]int, 1000) // 500..1499
	for i := range a {
		a[i], b[i] = i, i+500
	}
	out1, work1 := commonScan(a, b)
	out2, work2 := commonSet(a, b)
	fmt.Println("scan:", len(out1), "common values,", work1, "steps")
	fmt.Println("set: ", len(out2), "common values,", work2, "steps")
}

scan: 500 common values, 625250 steps
set:  500 common values, 2000 steps