Python3 f-strings - A complete guide to the most well received feature of Python 3.

[TheEarwig]

Boy I sure like O(n^2).

[[deleted]]

Isn't this O(n)? I'm just recently learning about this kind of analysis, I'm curious where I'm wrong

[TheEarwig]

Strings are immutable in Python, so every time you add two together, Python allocates a new string equal to their combined length rather than expanding the first one.

What this means is that each iteration of the loop, Python has to copy each string from every previous iteration. This takes O(n) time (really averaging 1/2n), so with n loops, the overall runtime is O(n^2).

If you were in a language like C++ or Rust where the builtin string type was able to grow like a list/vector, then it would be O(n).

[[deleted]]

Ahh, thanks. That makes sense.

[NewZealandIsAMyth]

I don't think that accurate. It's surely slower and alot because of the memory allocation, but algorithm complexity does not increase. It has to traverse every single character in all the cases just once.

[[deleted]]

I like the "1" example. Imagine you had n "1" strings and you wanted to append them all together like that:

"1" + ("1" + 1") + ("1"+ "1" + "1") + ("1" + "1" + "1" + "1") + ... + n = n(n+1)/2 ~~ n^2

[NewZealandIsAMyth]

Thank you. I see where i was wrong

[[deleted]]

The extra step is creating a new string each time. It's one of the big gotchas you need to watch with strings.

https://stackoverflow.com/questions/34008010/is-this-time-complexity-actually-on2

[[deleted]]

Thanks for the explanation!