x/website: incorrect time complexity

[mkraft]

URL: https://go.dev/doc/effective_go#interfaces

The method (Sequence).String is mistakenly said to have a quadratic time complexity but it's actually linear, or O(N).

Relevant quotes:

Loop is O(N²); will fix that in next example.

and

It also has complexity O(N²), which is poor.

[Merovius]

No, the complexity is quadratic - specifically O(n•(log(n)+m)), where n is the length of the Sequence and m is the maximum length of the string¹. str += fmt.Sprint(elem) is O(m) and it's executed n times. Additionally, the slice gets copied (O(n)) and sorted (O(n•log(n))).

[1] edit to clarify: the total length of the concatenated string - that is, the sum of the lengths of all the strings in the sequence.

[Merovius]

Note, specifically, that s += x has to a) allocate a buffer of length len(s)+len(x), b) copy over s and c) copy over x. Which is why it has that complexity.

If the loop used append (or strings.Builder), the function would be O(n•log(n)), as append has amortized constant cost (i.e. you only have to allocate+copy, if the appended thing doesn't fit in the extra capacity reserved).

But string concatenation doesn't have extra capacity - it can't, because otherwise adding two different things to a single string would clobber each other (just like append does). So this isn't an "implementation inefficiency" either (well, a sufficiently clever compiler could recognize the loop pattern and optimize it).

[mvdan]

Closing per the above.

[mkraft]

@Merovius Thank you, I didn't realize that str += fmt.Sprint(elem) was O(m). However, the sorting only happens once, so why multiply it by n to get O(n*(log(n)+m))? Isn't the complexity just O(n*m)?

[Neurostep]

@mkraft sorting in O(nlog n), string concatenation is O(nm). O(nlog n) + O(nm) = O(n*(log n + m))

[Merovius]

@mkraft In part, the issue is that I got confused. The cost is (where n is the number of elements, k is the maximum length of the strings in the list):

1. O(n) for copying (you only copy string header, which is O(1), but you copy n of them)
2. O(n•log(n)•k) for sorting (you have O(n•log(n)) string comparisons to sort and each takes O(k) time)
3. O(n²•k) for the looped concatenation (see below).

Part of my confusion was that k-factor (I think the m I used above isn't helpful). The justification for O(n²k) is that s+=x is (as I said above) O(len(s)+len(x)) - and s grows successively. So the first loop run is O(len(s[0])), the second is O(len(s[0])+len(s[1])), the third is O(len(s[0])+len(s[1])+len(s[2]) and so on. s[i]≤k, so you get for the entire loop

O(k+2k+…+n•k) = O(k•(1+2+…+n)) = O(k•n•(n+1)/2) = O(k•n²) (See also)

So, for the entire function, you get O(n+n•log(n)•k+n²•k). You are correct that, asymptotically, log(n)≤n≤n², so this simplifies to O(n²•k). I included the log(n) for taste, but it indeed doesn't matter for the complexity class.

Anyways, algorithmic complexity is kind of confusing to get right, sometimes. But really, the relevant factor is that every time you go through the loop, you have to re-do all the copying you already did in the past. That's where the quadratic factor comes from.

[Merovius]

That seems correct.

I suggest moving any further questions or discussions to a more appropriate forum, e.g. reddit, golang-nuts or slack. The issue tracker is not really well-suited or intended for this.