Why built-ins matter for Big O
A call such as slices.Contains(nums, x) is a single line, but it is not a single step. When you count the cost of your code, every call to a built-in function or a standard-library function counts as the work it does inside. A loop of n passes that calls an O(n) function is O(n²), even though only one loop is visible.
This lesson lists what the common Go functions cost, where n is the length of the slice, string or map involved.
Built-in functions
| Call | Time | Notes |
|---|---|---|
len(x), cap(x) | O(1) | The length is stored with the value. |
append(s, v) | O(1) amortized | Occasionally copies the whole array into a bigger one. |
append(s, t...) | O(len(t)) amortized | Cost follows the number of elements added. |
copy(dst, src) | O(k) | k is the number of elements copied. |
make([]int, n) | O(n) | The new memory is filled with zeros. |
m[k], m[k] = v, delete(m, k) | O(1) average | A map is a hash table. |
min(a, b), max(a, b) | O(1) | Built in since Go 1.21. |
Standard-library functions
| Call | Time |
|---|---|
sort.Ints(xs), slices.Sort(xs) | O(n log n) |
sort.SearchInts(xs, x), slices.BinarySearch (sorted input) | O(log n) |
slices.Contains(xs, x), slices.Index(xs, x) | O(n) |
slices.Reverse(xs), slices.Max(xs), slices.Clone(xs) | O(n) |
strings.Contains(s, t), strings.Index(s, t) | Grows with the length of s |
strings.Split(s, sep), strings.Join(parts, sep), strings.Repeat(s, k) | Proportional to the size of the result |
A short program shows a few of them in action:
xs := []int{5, 2, 9, 1}
sort.Ints(xs)
fmt.Println(xs, sort.SearchInts(xs, 9), slices.Contains(xs, 2), slices.Index(xs, 5))
slices.Reverse(xs)
fmt.Println(xs)
[1 2 5 9] 3 true 2
[9 5 2 1]
The sort costs O(n log n), and after it the binary search finds 9 at index 3 in O(log n). The linear searches Contains and Index work on any slice, sorted or not, but may look at every element.
Working out a whole function
Suppose a function removes duplicates like this: for each element of nums, it calls slices.Contains(result, v) and appends v to result if the answer is false. The loop runs n times. The Contains call scans a slice that can grow to n elements, so it is O(n), and the append is O(1) amortized. The loop multiplies the two, so the function is O(n²). Replacing result lookups with a map[int]bool makes each check O(1) on average and the function O(n), at the price of O(n) extra memory.
The habit to build is to ask two questions of every line inside a loop: what does this call do internally, and how large is the data it touches?
Go-specific points
- Amortized is not worst case. One
appendcan copy the whole array. In a loop ofnappends the total is stillO(n), because each growth step doubles the capacity for small slices and grows more slowly for large ones, so copies become rare. You can avoid them by creating the slice withmake([]int, 0, n)when you know the final size. - Map iteration order is random, and a loop over a map is
O(n)in its size. Never rely on the order. - Sorting changes the slice in place.
sort.Intsreturns nothing and modifies its argument. The binary search functions only give a correct answer on sorted data. - Strings are immutable. Functions like
strings.Repeatandstrings.Joinbuild a new string, so their cost includes writing every byte of it.
Common mistakes
- Searching a slice inside a loop. For each of
nitems,slices.Contains(other, item)costsO(n), so the whole thing isO(n²). Putting the elements ofotherin a map first makes each lookupO(1)on average and the totalO(n). - Sorting inside a loop. Sort once before the loop if you can.
- Assuming
lenof a string counts characters. It returns the byte length in constant time.len("héllo")is 6, while the number of runes is 5, and counting runes withutf8.RuneCountInStringtakesO(n).
Key takeaways
- A built-in call costs whatever it does inside; check before you put it in a loop.
len, indexing and map operations are constant time; searching and copying are linear; sorting isO(n log n).- Binary search is
O(log n)but needs sorted data. - When a function is slower than expected, look for a linear library call hidden inside a loop.