Slices: what is fast and what is slow
A slice is a view onto an array, so its cost profile follows the array's:
- Reading or writing by index is
O(1). - Appending at the end is
O(1)amortized. - Searching for a value in an unsorted slice is
O(n), because any element might be the one. - Inserting or deleting in the middle is
O(n), since the elements after the position must shift.
Go has no insert or delete method on slices, so you build them from append:
q := []int{1, 2, 3, 4, 5}
q = append(q[:1], q[2:]...)
fmt.Println(q)
q = append([]int{0}, q...)
fmt.Println(q)
[1 3 4 5]
[0 1 3 4 5]
The first line removes the element at index 1 by shifting everything after it one place left. The second puts a new element at the front by building a new slice. Both touch up to n elements. Doing either inside a loop over the same slice gives O(n²).
The deletion also reuses the original array, so the old slice q was changed in place; a second slice made earlier from the same array would see the shifted values.
Strings: bytes and runes
A Go string is an immutable sequence of bytes, usually UTF-8 text. That has consequences for the cost:
len(s)isO(1)and gives the number of bytes.s[i]isO(1)and gives one byte, not a character.- A
rangeloop over a string decodes it rune by rune and gives the byte position of each one, so it costsO(n). - Counting the characters with
utf8.RuneCountInString(s)isO(n), because the whole string must be decoded.
s := "héllo"
fmt.Println(len(s), utf8.RuneCountInString(s), s[1], string(s[0]))
for i, r := range s {
fmt.Print(i, ":", string(r), " ")
}
6 5 195 h
0:h 1:é 3:l 4:l 5:o
The letter é takes two bytes, so the string has length 6 and 5 runes, s[1] is the first byte of é (195), and the next rune starts at byte 3.
Comparing two strings with == is also not free. Go first checks the lengths, and if they match it compares byte by byte, so the cost is O(n) in the worst case, when the strings are equal or differ only near the end. Comparing a string against many others in a loop therefore multiplies that cost by the number of comparisons.
What a logarithm is
The logarithm base 2 of n answers the question: how many times can you halve n before you reach 1? A loop that halves a number counts it:
func halvings(n int) int {
steps := 0
for n > 1 {
n /= 2
steps++
}
return steps
}
| n | halvings(n) |
|---|---|
| 8 | 3 |
| 1,000 | 9 |
| 1,000,000 | 19 |
| 1,000,000,000 | 29 |
The loop gives the logarithm rounded down. A billion is only about 30 halvings away from 1, so an O(log n) algorithm is nearly as good as constant time. The base is dropped in Big O, because changing the base only multiplies by a constant.
Binary search: a logarithmic algorithm
On a sorted slice, you can look at the middle element and discard half of the range every time:
func binarySearch(sorted []int, target int) int {
lo, hi := 0, len(sorted)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if sorted[mid] == target {
return mid
} else if sorted[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1
}
On a sorted slice of a million integers, this loop runs at most 20 times, whether the value is found or not. A linear search could need a million comparisons. The condition is that the data is sorted: sorting costs O(n log n), so it pays off only when you search many times.
Key takeaways
- Slice indexing and appending are cheap; inserting and deleting away from the end cost
O(n). - String length and byte indexing are
O(1), but counting characters or ranging over runes isO(n). - A logarithm counts halvings;
O(log n)grows extremely slowly. - Binary search needs sorted input and runs in
O(log n).