0

Given a string word, I'm trying to estimate the Big-O time complexity of the following function.

def wildcards(word: str) -> Iterator[str]:
    for j in range(len(word)):
      yield f"{word[:j]}_{word[j + 1:]}"

I've read Is the time-complexity of iterative string append actually O(n^2), or O(n)? and Time complexity of string concatenation in Python, both of which are concerned with repeated string concatenation, which isn't happening here.

This answer says slicing is linear in size of the slice, so, two slices takes O(n) time in total. But what about the f-string?

Overall, it looks to me that wildcards is O(n2), is that right?

Abhijit Sarkar
  • 21,927
  • 20
  • 110
  • 219
  • What are the generated strings used for? Depending on the use case you may not need to actually make *n* copies of the input string but simply keep track of the incrementing index of the underscore to improve the overall time complexity to *O(n)*. – blhsing Jul 12 '23 at 02:18

1 Answers1

0

This is O(n²) time complexity and O(n) space complexity, but not because of the f-string.

You have an outer loop over the length of the string:

for j in range(len(word)):
    ...

Then, string slicing is nested inside this loop, which is also an O(n) copy of the string on each iteration.

Note that just wildcards(word) is O(1), because just creating the generator doesn't do anything, so it's only O(n²) if you're actually consuming the generator.

wim
  • 338,267
  • 99
  • 616
  • 750
  • What actually happens here `f"{word[:j]}_{word[j + 1:]}"`? The two slices are created (`O(n)`) and then f-string creates a new string by copying over the characters (`O(n)`)? – Abhijit Sarkar Jul 12 '23 at 02:05
  • Yes, but 3x _O(n)_ is still _O(n)_. – wim Jul 12 '23 at 02:12