Yes, in your case^*1 string concatenation requires all characters to be copied, this is a O(N+M) operation (where N and M are the sizes of the input strings). M appends of the same word will trend to O(M^2) time therefor.

You can avoid this quadratic behaviour by using str.join():

word = ''.join(list_of_words)

which only takes O(N) (where N is the total length of the output). Or, if you are repeating a single character, you can use:

word = m * char

You are prepending characters, but building a list first, then reversing it (or using a collections.deque() object to get O(1) prepending behaviour) would still be O(n) complexity, easily beating your O(N^2) choice here.

^*1 As of Python 2.4, the CPython implementation avoids creating a new string object when using strA += strB or strA = strA + strB, but this optimisation is both fragile and not portable. Since you use strA = strB + strA (prepending) the optimisation doesn't apply.

The python page on time-complexity shows that slicing lists has a time-complexity of O(k), where "k" is the length of the slice. That's for lists, not strings, but the complexity can't be O(1) for strings since the slicing must handle more characters as the size is increased. At a guess, the complexity of slicing strings would also be O(k). We can write a little bit of code to test that guess:

import time

StartSize = 2097152

size = StartSize
for _ in range(10):
    # create string of size "size"
    s = '*' * size

    # now time reverse slice
    start = time.time()
    r = s[::-1]
    delta = time.time() - start

    print(f'Size {size:9d}, time={delta:.3f}')

    # double size of the string
    size *= 2

This uses a simple method of timing. Other tools exist, but this is simple. When run I get:

$ python3 test.py
Size   2097152, time=0.006
Size   4194304, time=0.013
Size   8388608, time=0.024
Size  16777216, time=0.050
Size  33554432, time=0.098
Size  67108864, time=0.190
Size 134217728, time=0.401
Size 268435456, time=0.808
Size 536870912, time=1.610
Size 1073741824, time=3.192

which shows the time doubles when doubling the size of the string for each reverse slice. So O(n) (k == n for whole-string slicing).

Edit: spelling.

It's a combination of Boyer-Moore and Horspool.

You can view the C code here:

Fast search/count implementation, based on a mix between Boyer-Moore and Horspool, with a few more bells and whistles on the top. For some more background, see: https://web.archive.org/web/20201107074620/http://effbot.org/zone/stringlib.htm.

From the link above:

When designing the new algorithm, I used the following constraints:

• should be faster than the current brute-force algorithm for all test cases (based on real-life code), including Jim Hugunin’s worst-case test
• small setup overhead; no dynamic allocation in the fast path (O(m) for speed, O(1) for storage)
• sublinear search behaviour in good cases (O(n/m))
• no worse than the current algorithm in worst case (O(nm))
• should work well for both 8-bit strings and 16-bit or 32-bit Unicode strings (no O(σ) dependencies)
• many real-life searches should be good, very few should be worst case
• reasonably simple implementation

The running time of string concatenation depends on how it is implemented. It is impossible to tell whether new_word += i takes $O(1)$ or $\Theta(|\text{new_word}|)$ or anything else unless you know more about Python. Moreover, looking around stackoverflow, it seems that the complexity depends on which version of Python you are using.

In contrast, it is quite clear that the procedure uses $\Theta(|\text{word}|+1)$ space, since it builds new_word from scratch, not reusing the memory of word. This has nothing to do with the loop; the statement new_word = word[:], which makes a copy of word, also uses up $|\text{word}|$ space. Space consumption is the amount of memory used. If you're constructing a new string of length $|\text{word}|$, then it uses up memory proportional to $|\text{word}|$.

I suggest forgetting about what you call the "mathematical perspective", and focusing instead on the intuitive meaning of time and space complexity. Time complexity is the number of instructions executed by the program. Space complexity is the amount of memory that needs to be allocated in order to run the procedure. You are stating some rules for calculating these quantities, but it's much more important for you to understand what you are calculating rather than specific tricks which are dubious when applied mechanically.

The relevant code is here and it is O(k) as it can be seen line 1628

result_buf = PyBytes_AS_STRING(result);
for (cur = start, i = 0; i < slicelength;cur += step, i++) {
        result_buf[i] = source_buf[cur];
}
return result;

As can be seen from the source code, the implementation of int.__str__ has runtime complexity of O(m*n) where m is the number of binary digits and n is the number of decimal digits. Since for an integer i the number of digits in an arbitrary base b is given by log(i, base=b) and logarithms in different bases differ only by a constant, the runtime complexity is O(log(i)**2), i.e. quadratic in the number of digits.

This can be verified by running a performance test:

import perfplot

perfplot.show(
    setup=lambda n: 10**n,
    kernels=[str],
    n_range=range(1, 1001, 10),
    xlabel='number of digits',
)

The quadratic time complexity in the number of digits is also mentioned in the issue for CVE-2020-10735:

[...] A huge integer will always consume a near-quadratic amount of CPU time in conversion to or from a base 10 (decimal) string with a large number of digits. No efficient algorithm exists to do otherwise.

Semantically the line concat += word creates a new string containing the concatenation of concat and word and then re-assigns concat to refer to that new string. This would make the runtime of your loop quadratic because creating this new string takes time linear in the lengths of both concat and word.

However, in the actual implementation CPython optimizes this to mutate the contents of concat instead of creating a new string if and only if concat is the only reference to the string. Appending to a string in-place takes time that is only linear in the length of word (amortized). This makes the runtime of your loop linear. But, as I said, this optimization can only be applied if concat is the only reference to the string (otherwise the value of other variables would change as well, which would break the semantics). So introducing another reference to the string with temp = concat prevents the optimization.