为什么这段代码在Go O（n²）中而不是O（n）中？

Question

I'm in the middle of reading Effective Go, and there is a piece of code which I think is O(n) complexity yet it is O(n²). Why is this for range loop considered to be O(n²)?

It is found here (under #interfaces)

type Sequence []int
...
func (s Sequence) String() string {
    ...
    for i, elem := range s { // Loop is O(N²); will fix that in next example.
        if i > 0 {
            str += " "
        }
        str += fmt.Sprint(elem)
    }
    ...
}

The reason I think it is O(n) is because there is only one iteration over s, and the if statement and fmt.Sprint should not be in O(n) complexity.

Answer 1

Every time you concatenate str += fmt.Sprint(elem) you create a new String that has to transfer (copy) the characters of the prev str into the new one. In step 1 you copy 1 char, in step 2, 2, etc. This gives n(n+1)/2 copies. Hence the complexity is O(n^2).