Include time and space complexity in documentation

Ideas
22

Few things that might be useful to add:

  1. str.rfind doesn’t use two-way and is subject to O(n^2) worst case. This implements it, but uncertain when it is going to merged - not an issue in practice.
  2. difflib’s longest common substring implementation is worst case O(n^2). I think this is the only algorithm in stdlib from the family of sequence alignment (apart from private _suggestions Levenstein DP score). Thought of replacing it with O(n) so to have a proper LCSUB that users can rely on (this has been brought up several times), but decided to wait until there is a dedicated place for sequence algorithms. Current implementation is good enough for the difflib’s approach.
  3. list.sort is adaptive - O(n) best case. A lot of cases run faster than O(nlogn).
2 Likes
Algorithmic complexity of difflib