Is taking a substring in python an O(n) operation? [duplicate]

Question

In C++ if I were to remove the first character from a string it would look something like:

string s = "myreallylongstring";
s = s.substr(1);

and this would be O(1). [correct me if I'm wrong about that]

However in Python's "immutable string" world, does this code run in O(n)?

s = "myreallylongstring"
s = s[1:]

Would it be any faster if I used a list of chars instead?

Answer 1

Slicing any built-in type in Python (aside from memoryview) is O(n) in the general case (main exception being a complete slice of immutable instances, which usually returns the original instance without copying it, since it's not needed).

A list of characters wouldn't help; removing a character from the beginning of a list is O(n) (it has to copy everything above it down a slot). A collections.deque could conceivably improve the big-O (they can do O(1) pops from either end), but it would also consume substantially more memory, and more fragmented memory, than the string.

For all but the largest strings, you're usually okay even with these O(n) inefficiencies, so unless you've actually profiled and found it to be a cause of problems, I'd stick with the slicing and let it be.

That said, you're wrong about C++; s = s.substr(1) is no different from Python's s = s[1:]. Both of them end up copying the entire string save the first character, C++ move assigns back to the original string, while Python replaces the original name binding to the old object with the new one (functionally pretty similar operations). s.substr(1) isn't even using std::string's mutability features; s.erase(0, 1) would in fact erase in-place, mutating the original string, but it would still be O(n) because all the other characters would have to be copied down into the space previously consumed by the deleted characters (no std::string implementation that I know of allows for the storage of an offset from the beginning of the string to find the real data, the pointer to the data points to the first allocated byte at all times).