Start learning free

GO · BIG O NOTATION

Time Complexity Guidelines in Go, explained

What constant time means

An operation runs in constant time, written O(1), when the number of steps does not depend on the size of the input. A slice with ten elements and a slice with ten million elements take the same effort. The work isn't necessarily small, only fixed.

Constant time is the best case you can ask for. Knowing which Go operations have it tells you which lines are safe to put inside a loop.

Operations that take O(1) in Go

  • Arithmetic and comparisons on numbers: a + b, a * b, a < b, a % 2 == 0.
  • Reading or writing a slice element by index: nums[i] and nums[i] = x. The index is converted to a memory address with one multiplication and one addition.
  • len and cap on slices and strings, and len on maps. The lengths are stored, not counted.
  • Reading a byte of a string: s[i].
  • Map lookup, insert and delete: m[k], m[k] = v and delete(m, k) take O(1) on average, because a map is a hash table. The worst case is higher, but for ordinary keys you can treat them as constant.
  • Appending to the end of a slice, nums = append(nums, x), is O(1) amortized. Most appends write one element. Occasionally the array is full, and append allocates a bigger one and copies the old elements. Spread over many appends, the average cost per append is still constant.
  • Slicing, nums[a:b], takes constant time, because it creates a new slice header that points into the same array and copies no elements. Slicing a string works the same way.
  • Passing a slice or a map to a function copies only a small header, not the data.
  • Taking the larger of two values with the built-in max(a, b) and the smaller with min(a, b).

An example

func firstAndLast(nums []int) (int, int) {
    return nums[0], nums[len(nums)-1]
}

This function reads two elements and calls len once, so it takes the same time for any non-empty slice. Called on an empty slice, it panics with an "index out of range" error. Constant time says nothing about correctness, so check the empty case separately.

Guidelines for reading complexity

  • Count loops, not lines. A function made only of constant-time operations is O(1), however many lines it has. Ten constant statements are still constant.
  • Drop constants. O(5) and O(1000) are both written O(1). Likewise, a loop that always runs exactly 26 times is O(1).
  • A loop over the input breaks the pattern. If the number of passes depends on len(nums), the function is at least O(n).
  • Add steps that run one after another; multiply steps that are nested. An O(1) step followed by an O(n) loop is O(n). A loop of n passes containing an O(n) step is O(n²).
  • Keep only the largest term. O(n + 1) is O(n).

Common mistakes

  • Assuming a single line is constant. copy(dst, src) and slices.Contains(nums, x) each look like one step, but both do work proportional to the slice length.
  • Treating a small fixed loop as linear. Checking the four neighbours of a grid cell is four steps, so it is O(1).
  • Thinking a slice expression copies. Because nums[1:4] shares the original array, writing to the new slice changes the original too. For example, with a := []int{1, 2, 3, 4, 5} and b := a[1:4], setting b[0] = 99 turns a into [1 99 3 4 5]. The speed comes from the sharing.
  • Forgetting the empty case. An operation like nums[len(nums)-1] is constant time, but on an empty slice it indexes at -1 and panics.

Key takeaways

  • O(1) means the cost does not grow with the input size.
  • Indexing, len, map operations (on average), slicing and amortized append are all constant-time in Go.
  • Constants and smaller terms are dropped when writing Big O.
  • Look for loops over the input, and for library calls that hide one, before you call a function constant time.
Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free