2

Why does f work much faster than g?

def f(n):
    s = ''
    for i in range(n):
        s = s + 'x'
    return s

def g(n):
    s, t = '', ''
    for i in range(n // 2):
        s = t + 'x'
        t = s + 'x'
    return t

print(len(f(500000))) - 0.1s
print(len(g(500000))) - 7.684s

Return values are the same. Why f has linear complexity, but g quadratic?

Chris_Rands
  • 35,097
  • 12
  • 75
  • 106
petrush
  • 885
  • 7
  • 20
  • 7
    CPython has a special case optimization for the case of `x += y` or `x = x + y` where `x` and `y` are a `str` (`y` can be an expression that results in a `str`, e.g. `x += 'a' + 'bcd'`) and there are no other references to it; CPython mutates the `str` in place (technically against the rules, but with no other references, it's not breaking observed behaviors). – ShadowRanger Jun 22 '18 at 09:49
  • Yes ShadowRanger wrote an excellent related answer here https://stackoverflow.com/a/40996908/6260170 – Chris_Rands Jun 22 '18 at 11:22
  • Incidentally, the *time complexity* isn't changing I think, although the *computation time* is – Chris_Rands Jun 22 '18 at 11:23
  • @Chris_Rands: It really does change if the strings are overallocated for the purpose. – Davis Herring Jun 22 '18 at 21:17

0 Answers0