Go Time Complexity for Interviews

Updated · By

Go's documentation states few costs. container/heap gives O(log n) for Push, Pop, Remove and Fix and O(n) for Init, slices.Insert and slices.Delete are linear, and sort.Sort makes O(n*log(n)) calls to Less and Swap. It states nothing for map operations or for append, so call those average-case and amortized assumptions about the current runtime, and say so.

Where these figures come from

Go has three kinds of official document to check: the language specification, the standard library's package pages on pkg.go.dev, and the Go blog. All were read on November 12, 2026: the specification for Go 1.27, and the package pages for go1.27.4.

Unlike Python or Rust, Go publishes no table of costs. A few functions state one in a sentence, and those are the figures below. Where the documents say nothing, this page says so instead of filling the gap, and the last section lists what is missing.

Slices and append

A slice is a view of an array. The specification says it "shares storage with its array and with other slices of the same array," so slicing copies nothing. The functions in the slices package that state a cost are Insert and Delete.

OperationCostWhat the docs say
slices.Insert(s, i, v...)O(len(s) + len(v))"This function is O(len(s) + len(v))." The elements at s[i:] are shifted up.
slices.Delete(s, i, j)O(len(s) - i)Delete many items in one call rather than one at a time, the docs advise.
append(s, x)Not statedThe spec: if the capacity is not large enough, "append allocates a new, sufficiently large underlying array." Otherwise it reuses the array.
s[i:j]Not statedThe result shares the original array, so nothing is copied.
slices.Contains, slices.IndexNot statedDescribed only as reporting whether, or where, a value is present.
slices.BinarySearchNot statedRequires a slice "sorted in increasing order." The docs give no figure.

How much a new array grows is not in the specification. In the current runtime (growslice in runtime/slice.go, Go 1.27), a slice with fewer than 256 elements of capacity doubles, and a larger one grows by about 1.25 times plus a constant. Geometric growth like that is what makes append amortized O(1), but it is the implementation's choice, not a promise. When you know the final size, make([]T, 0, n) or slices.Grow avoids the reallocations entirely.

Maps

No Go document gives a cost for map lookups, inserts or deletes. The Go blog's Go maps in action says "Go provides a built-in map type that implements a hash table," and that is what you can reason from: constant time on average, as an assumption about a hash table, not a stated bound.

Two documented facts are worth knowing. Since Go 1.24 the map is a Swiss Table, and the blog post on it, Faster Go maps with Swiss Tables, says Go maps "grow incrementally, so that each insertion has an upper bound on the amount of growth work it must do." Each map is split into tables of at most 1024 entries, so one insert copies at most 1024 entries, never the whole map. And the specification says "the iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next," so never rely on it.

Sorting

The sort package states its costs as numbers of calls, and since Go 1.19 "the sorting algorithm has been rewritten to use pattern-defeating quicksort." The slices package has the newer generic sorts, which the sort package's own notes call "more ergonomic" and faster "in many situations," but they state no figures.

FunctionCostStable
sort.Sort(data)O(n*log(n)) calls to Less and Swap"Not guaranteed to be stable."
sort.Stable(data)O(n*log(n)) calls to Less, O(n*log(n)*log(n)) calls to SwapYes
sort.Slice(x, less)Not stated"Not guaranteed to be stable: equal elements may be reversed from their original order."
slices.Sort, slices.SortFuncNot statedSortFunc is "not guaranteed to be stable."
slices.SortStableFuncNot statedYes, it keeps "the original order of equal elements."
sort.Search(n, f)Not stated"Uses binary search" and calls f(i) only for i in [0, n).

container/heap

container/heap is the one package with a cost on every function. You supply the storage by implementing heap.Interface on your own type, usually a slice, and the package keeps it in heap order. It is a min-heap by Less: "The minimum element in the tree is the root, at index 0."

FunctionCostNote
heap.Init(h)O(n)Builds heap order over existing data.
heap.Push(h, x)O(log n)
heap.Pop(h)O(log n)Removes and returns the minimum by Less.
heap.Remove(h, i)O(log n)You need the element's index.
heap.Fix(h, i)O(log n)After changing element i. Cheaper than Remove followed by Push, the docs say.
Reading the minimum, h[0]O(1)An index into your own slice.

In every row, n is h.Len(), as the docs define it. For a max-heap, reverse the comparison in your Less method.

Strings and strings.Builder

The specification says strings are immutable and that "string addition creates a new string by concatenating the operands." It gives no cost, but each += in a loop builds a new string from the old one, so the copying adds up to quadratic in the total length. The strings package offers strings.Builder, which "is used to efficiently build a string using Builder.Write methods. It minimizes memory copying." Neither states a Big O.

Indexing a string, s[i], reads a byte, not a character. A string holding non-ASCII text needs for i, r := range s or a conversion to []rune to work with characters.

Common interview traps

Each of these follows from a statement above, and each is a place where a correct Go solution quietly gets slower or wrong.

Go

package choices

import (
	"container/heap"
	"strings"
)

// 1. Appending without a capacity: the backing array is reallocated and
// copied as it grows. Give make the final size when you know it.
func squares(n int) []int {
	out := make([]int, 0, n) // one allocation, no copying on append
	for i := 0; i < n; i++ {
		out = append(out, i*i)
	}
	return out
}

// 2. append reuses the base array when it has spare capacity, as the spec
// says, so two results appended from one shared base can overwrite each
// other's last element. Copy first when the base is shared.
func withSuffix(base []int, x int) []int {
	out := make([]int, len(base), len(base)+1)
	copy(out, base)
	return append(out, x)
}

// 3. += on a string in a loop copies everything built so far each time.
func joinWords(words []string) string {
	var b strings.Builder
	for _, w := range words {
		b.WriteString(w)
	}
	return b.String()
}

// 4. container/heap: call heap.Push and heap.Pop, never the methods on
// your type directly. The methods only append and truncate the slice.
type minHeap []int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// The k largest values with a heap of size k: O(n log k).
func topK(values []int, k int) []int {
	h := &minHeap{}
	for _, v := range values {
		heap.Push(h, v)
		if h.Len() > k {
			heap.Pop(h) // drop the smallest
		}
	}
	return *h
}

The heap package's own docs carry the warning in point 4: "Push and Pop in this interface are for package heap's implementation to call. To add and remove things from the heap, use heap.Push and heap.Pop." Two more traps need no code: iterating over a map in a fixed order (the order is unspecified), and sort.Slice when equal elements must keep their order (it is not stable).

How to say it out loud

What a strong candidate might say

I'll count with a map. Go doesn't document a cost for maps, but it's a hash table, so I'm assuming constant time on average and the pass is O(n). I'll create the result slice with make and a capacity of n, so append never has to reallocate. For the top k I'll use container/heap with a heap of size k, where the docs give O(log n) for Push and Pop, so that part is O(n log k).

What a strong candidate might say

I'm using sort.SliceStable here rather than sort.Slice, because I sort by score after sorting by name, and sort.Slice isn't guaranteed to keep equal elements in order.

Saying which figures are documented and which are assumptions is the habit interviewers notice. You can practice it in a coding mock interview, and the Big O cheat sheet covers how to derive the rest.

What the docs do not state

These have no figure in the specification or the package pages read for this guide, so none has a cost above:

  • Maps: lookup, insert, delete, len and iteration. Only the per-insert bound on growth work, from the blog, is documented.
  • append: no cost, amortized or otherwise. The growth rule is in the runtime source, not the specification.
  • sort.Slice, slices.Sort, slices.SortFunc and slices.SortStableFunc: no figure, only stability.
  • slices.Contains, slices.Index and slices.BinarySearch: no figure.
  • String concatenation with + and strings.Builder: no figure.

Complexity by language

Each language page takes its figures from that language's own documentation, cites it, and says what the documentation leaves out. TypeScript runs as JavaScript, so its costs are on the JavaScript page.

For the structures and algorithms themselves, see the Big O cheat sheet and sorting algorithm complexity.

Frequently asked questions

Is a Go map lookup O(1)?

Go does not document a cost for maps. The Go blog describes the built-in map as a hash table, so treat a lookup as constant time on average and say it is an assumption. Since Go 1.24, maps grow one table of at most 1024 entries at a time, which bounds the growth work any single insert does.

Is append O(1) in Go?

Not by any documented promise. The specification says only that append allocates a new, sufficiently large array when the capacity runs out. The current runtime doubles small slices and grows large ones by about 1.25 times, which makes append amortized constant in practice. When you know the size, preallocate with make.

What is the time complexity of container/heap in Go?

The package documents it: Push, Pop, Remove and Fix are O(log n) and Init is O(n), where n is h.Len(). Reading the minimum is an index into your own slice at position 0. Always call heap.Push and heap.Pop rather than the methods on your type.

Is sort.Slice stable in Go?

No. Its documentation says the sort is not guaranteed to be stable, so equal elements may be reversed from their original order. Use sort.SliceStable or slices.SortStableFunc when ties must keep their order.

Know the complexities? Now explain them out loud.

3 interviews a month on the Free plan, up to 20 minutes each. No card needed.