A couple of places in the String docs states that an operation is O(n), usually when discussing a method that needs to shift elements over. However, this is not helpful to users who do not know O-notation, and n is generally either misleading or undefined.
String::insert_str: The operation is really O(n-idx+k), where n is the length of self, and k is the length of string. In fact, that's not even true if the String needs to be resized. If we wanted to cover that, we'd need to include the "amortized" qualifier in there. O(n) is insufficient in part because if k is large and n is small, k is much more important. We probably want to ditch the O-notation here entirely, and just explain that it needs to shift everything after idx over, and copy in the characters from string, and that this operation may be slow because of it.
String::insert and String::remove: These are less egregious since O(n) is correct. However, the smaller bound of O(n-idx) can be given, and the difference might be significant. Here too, it'd be better to just get rid of the O-notation altogether and explain what happens instead.
A couple of places in the
Stringdocs states that an operation isO(n), usually when discussing a method that needs to shift elements over. However, this is not helpful to users who do not know O-notation, andnis generally either misleading or undefined.String::insert_str: The operation is reallyO(n-idx+k), wherenis the length ofself, andkis the length ofstring. In fact, that's not even true if the String needs to be resized. If we wanted to cover that, we'd need to include the "amortized" qualifier in there.O(n)is insufficient in part because ifkis large andnis small,kis much more important. We probably want to ditch the O-notation here entirely, and just explain that it needs to shift everything afteridxover, and copy in the characters fromstring, and that this operation may be slow because of it.String::insertandString::remove: These are less egregious sinceO(n)is correct. However, the smaller bound ofO(n-idx)can be given, and the difference might be significant. Here too, it'd be better to just get rid of the O-notation altogether and explain what happens instead.