What's the Big O Complexity of Go's `append` Function for Slices and Strings?

Examining the Big O of Append in Go

In Go, the builtin append function plays a crucial role in manipulating slices and strings. This article delves into the complexity of this function to shed light on its efficiency implications.

Understanding Reslicing in Slices

When appending to a slice, if the destination has sufficient capacity, Go performs a reslicing operation. This involves altering an integer within a struct to adjust the slice's length and capacity. However, if the destination lacks capacity, append must allocate new memory and copy the old contents, a process with potentially higher complexity.

Complexity of append with Slices

For slices with less than 1024 elements, the capacity is doubled with each append operation, yielding a linear time complexity of O(n), where n is the number of appends. For larger slices, the capacity increases by 1.25 per append, resulting in an O(log n) complexity.

String Concatenation with

In contrast to slices, strings are immutable in Go. This implies that every concatenation using creates a new string, copying the existing one. Consequently, when concatenating strings N times in a loop, you allocate N strings and copy memory N times, leading to a linear time complexity of O(n).

Hope for Constant Time Reslicing

The documentation briefly mentions "reslicing" as potentially a constant time operation for slices with sufficient capacity. However, it emphasizes that the actual implementation is implementation-specific. Based on the standard Go and gccgo implementations, reslicing is indeed a constant time operation in such cases.

The above is the detailed content of What's the Big O Complexity of Go's `append` Function for Slices and Strings?. For more information, please follow other related articles on the PHP Chinese website!