New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
x/website: incorrect time complexity #58982
Comments
No, the complexity is quadratic - specifically [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. |
Note, specifically, that If the loop used 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 |
Closing per the above. |
@Merovius Thank you, I didn't realize that |
@mkraft sorting in O(nlog n), string concatenation is O(nm). O(nlog n) + O(nm) = O(n*(log n + m)) |
@mkraft In part, the issue is that I got confused. The cost is (where
Part of my confusion was that
So, for the entire function, you get 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. |
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. |
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:
and
The text was updated successfully, but these errors were encountered: