What is the Time Complexity of Append and String Concatenation in Go?

Big O of Append in Go

This question delves into the complexity of the built-in append function and string concatenation in Golang. The original query also explores the efficiency of removing elements from a slice by appending two slices without including that element.

Append Complexity

According to the Golang documentation, if the destination slice has sufficient capacity, it will be resliced. Reslicing refers to the modification of an integer within the slice struct, which is a constant-time operation. However, if the slice has insufficient capacity, append will allocate new memory and copy the old one, resulting in an O(n) complexity, where n is the length of the slice.

String Concatenation

In contrast to slices, string concatenation using the operator is O(n^2) because strings are immutable in Go. Each string concatenation creates a new string, copying the old one. This results in the allocation of N strings and the copying of memory N times, where N is the number of concatenations.

Example

The provided example illustrates how to remove an element from a slice and highlights the constant time complexity of appending slices with sufficient capacity:

nums := []int{0, 1, 2, 3, 4, 5, 6, 7}
fmt.Println(append(nums[:4], nums[5:]...))

In this case, the reslicing operation is constant time because the destination slice has enough capacity to accommodate the new elements.

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