What is the Time Complexity of `append` in Go?

Append Complexity in Go

Problem:

What is the computational complexity of the following loop in Go?

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

Does append operate in linear time, or in amortized constant time?

Answer:

The Go Programming Language Specification states that append performs reallocation if necessary:

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

However, the specific algorithm to grow the target slice when necessary is implementation-dependent. For the current gc compiler, the algorithm is amortized constant time.

Amortized Constant Time Explanation:

The slice capacity is increased in a greedy manner:

• If the old capacity is greater than double the old capacity, the new capacity is set to the old capacity.
• Otherwise, if the old length is less than 1024, the new capacity is set to double the old capacity.
• Otherwise, the new capacity is increased by a quarter until it is at least the size of the old capacity.

This approach ensures that the total time spent reallocating is amortized to O(n), where n is the length of the resulting slice.

Implementation Considerations:

The Go language specification allows for different implementations of append. For example, the implementation may be generous (allocating more than the minimum necessary amount) or parsimonious (allocating the minimum necessary amount). The Go gc compiler uses a generous dynamic array amortized constant time algorithm.

Summary:

The complexity of append in Go depends on the implementation. However, common implementations like the Go gc compiler and gccgo use amortized constant time algorithms.

The above is the detailed content of What is the Time Complexity of `append` in Go?. For more information, please follow other related articles on the PHP Chinese website!