Is the time-complexity of iterative string append actually O(n^2), or O(n)?

by

In CPython, the standard implementation of Python, there’s an implementation detail that makes this usually O(n), implemented in the code the bytecode evaluation loop calls for + or += with two string operands. If Python detects that the left argument has no other references, it calls realloc to attempt to avoid a copy by resizing the string in place. This is not something you should ever rely on, because it’s an implementation detail and because if realloc ends up needing to move the string frequently, performance degrades to O(n^2) anyway.

Without the weird implementation detail, the algorithm is O(n^2) due to the quadratic amount of copying involved. Code like this would only make sense in a language with mutable strings, like C++, and even in C++ you’d want to use +=.

More Related Contents:

  1. Find common substring between two strings
  2. How slow is Python’s string concatenation vs. str.join?
  3. String concatenation without ‘+’ operator
  4. Find longest repetitive sequence in a string
  5. Python string ‘in’ operator implementation algorithm and time complexity
  6. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  7. Time complexity of string concatenation in Python [duplicate]
  8. How to test if one string is a subsequence of another? [duplicate]
  9. Python: find closest string (from a list) to another string
  10. String similarity metrics in Python [duplicate]
  11. Sliding window maximum in O(n) time
  12. String concatenation vs. string substitution in Python
  13. How can I interleave or create unique permutations of two strings (without recursion)
  14. What is the time complexity of heapq.nlargest?
  15. Finding the most frequent character in a string
  16. Is python += string concatenation bad practice?
  17. fastest method of getting k smallest numbers in unsorted list of size N in python?
  18. How can I remove duplicate words in a string with Python?
  19. Removing list of words from a string
  20. Convert string into Date type on Python [duplicate]
  21. How to use str.contains() with multiple expressions in pandas dataframes
  22. How to merge two json string in Python?
  23. What is the cost/ complexity of insert in list at some location?
  24. Use a string to call function in Python [duplicate]
  25. How does str(list) work?
  26. How to remove all integer values from a list in python
  27. Getting the subsets of a set in Python
  28. Why are str.count(”) and len(str) giving different outputs when used on an empty string?
  29. What is a “bytestring” (the `bytes` data type) in Python?
  30. Python- how to verify if a string ends with specific string?

Leave a Comment