Why is `len(string)` and `len(slice)` O(1) in Go?

Understanding the O(1) Time Complexity of len(string) and len(slice) in Go

The built-in function len() plays a crucial role in Go for determining the length of strings and slices. A question often arises whether these len() operations exhibit an O(1) time complexity.

Strings in Go

To understand why len(string) is O(1), we need to delve into the internal representation of strings in Go. A string in Go consists of a string header, which contains two fields: a pointer to the underlying character array and the string length. The len() function simply returns the string length stored in the string header, making it an O(1) operation.

Slices in Go

Similarly, slices in Go also have an O(1) len() operation. A slice is comprised of a pointer to the underlying array, a length, and a capacity. Just like strings, the len() function for slices returns the length field within the slice's header, resulting in an O(1) time complexity.

Source Code Analysis

You mentioned examining the builtin.go source code but encountered difficulty understanding it. This is understandable as the file contains documentation for the language's predeclared identifiers and does not provide direct insights into the implementation of len() for strings or slices.

Conclusion

The len() function for both strings and slices in Go has an O(1) time complexity. This is because the length information is readily available in the header structures associated with strings and slices, allowing for a constant-time retrieval.

The above is the detailed content of Why is `len(string)` and `len(slice)` O(1) in Go?. For more information, please follow other related articles on the PHP Chinese website!