The running time of string concatenation depends on how it is implemented. It is impossible to tell whether new_word += i takes or 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 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 space. Space consumption is the amount of memory used. If you're constructing a new string of length , then it uses up memory proportional to .

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.

Getting a slice is O(i_2 - i_1). This is because Python's internal representation of a list is an array, so you can start at i_1 and iterate to i_2.

For more information, see the Python Time Complexity wiki entry

You can also look at the implementation in the CPython source if you want to.

Short answer: str slices, in general, copy. That means that your function that does a slice for each of your string's n suffixes is doing O(n2) work. That said, you can avoid copies if you can work with bytes-like objects using memoryviews to get zero-copy views of the original bytes data. See How you can do zero copy slicing below for how to make it work.

Long answer: (C)Python str do not slice by referencing a view of a subset of the data. There are exactly three modes of operation for str slicing:

1. Complete slice, e.g. mystr[:]: Returns a reference to the exact same str (not just shared data, the same actual object, mystr is mystr[:] since str is immutable so there is no risk to doing so)
2. The zero length slice and (implementation dependent) cached length 1 slices; the empty string is a singleton (mystr[1:1] is mystr[2:2] is ''), and low ordinal strings of length one are cached singletons as well (on CPython 3.5.0, it looks like all characters representable in latin-1, that is Unicode ordinals in range(256), are cached)
3. All other slices: The sliced str is copied at creation time, and thereafter unrelated to the original str

The reason why #3 is the general rule is to avoid issues with large str being kept in memory by a view of a small portion of it. If you had a 1GB file, read it in and sliced it like so (yes, it's wasteful when you can seek, this is for illustration):

with open(myfile) as f:
    data = f.read()[-1024:]

then you'd have 1 GB of data being held in memory to support a view that shows the final 1 KB, a serious waste. Since slices are usually smallish, it's almost always faster to copy on slice instead of create views. It also means str can be simpler; it needs to know its size, but it need not track an offset into the data as well.

How you can do zero copy slicing

There are ways to perform view based slicing in Python, and in Python 2, it will work on str (because str is bytes-like in Python 2, supporting the buffer protocol). With Py2 str and Py3 bytes (as well as many other data types like bytearray, array.array, numpy arrays, mmap.mmaps, etc.), you can create a memoryview that is a zero copy view of the original object, and can be sliced without copying data. So if you can use (or encode) to Py2 str/Py3 bytes, and your function can work with arbitrary bytes-like objects, then you could do:

def do_something_on_all_suffixes(big_string):
    # In Py3, may need to encode as latin-1 or the like
    remaining_suffix = memoryview(big_string)
    # Rather than explicit loop, just replace view with one shorter view
    # on each loop
    while remaining_suffix:  # Stop when we've sliced to empty view
        some_constant_time_operation(remaining_suffix)
        remaining_suffix = remaining_suffix[1:]

The slices of memoryviews do make new view objects (they're just ultra-lightweight with fixed size unrelated to the amount of data they view), just not any data, so some_constant_time_operation can store a copy if needed and it won't be changed when we slice it down later. Should you need a proper copy as Py2 str/Py3 bytes, you can call .tobytes() to get the raw bytes obj, or (in Py3 only it appears), decode it directly to a str that copies from the buffer, e.g. str(remaining_suffix[10:20], 'latin-1').

It means the time it takes for something to happen doesn't depend on the size of the input. It deals with the subject of Time Complexity. As far as Python is concerned, list-slicing doesn't take constant time, it's bounded by a some kind of factor depending on the slice operation. You can refer to this page which documents the time complexity for common operations.

Anything with O(1) is something that's completed in constant time. The time complexity for get, set, and del slice operations are affected by either n, k, or some combination of those two. The page itself explains what those variables mean more concisely than I can, so refer to the introduction section for more information on those.

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;

O(n+k) is the average case, which includes having to grow or shrink the list to adjust for the number of elements inserted to replace the original slice.

Your case, where you replace the slice with an equal number of new elements, the implementation only takes O(k) steps. But given all possible combinations of number of elements inserted and deleted, the average case has to move the n remaining elements in the list up or down.

See the list_ass_slice function for the exact implementation.