News for hackers. Stuff that matters.
Re:Why Rust strings seem hard by deathanatos on Wednesday April 14, 2021 @07:48PM (#26814569)
> but only spend O(N lg N) time on copying the data around instead of O(N^2).

O(n) time copying, with doubling the buffer, not O(n log n)

It seems a bit counter intuitive, of course, that you can copy multiple times and have it still be O(n). The last copy will be n bytes. The second to last copy will be n / 2. The third to last, n / 4, etc.

  n + n/2 + n/4 + n/8 … = 2n
You end up copying, roughly, 2n bytes across all the buffer resizes, which is O(n).

There are no comments on this comment yet.