Complexity of creating list with concat operator in python

Question

I am starting to learn about data structures+algorithms, and I have encountered an issue. Here is the function I am testing:

def create_list_with_concat(n):
    l = []
    for i in range(n):
        l = l + [i]

Here is my thought process: I know that the concat operator is O(k) where k is the size of the list being added to the original list. Since the size of k is always 1 in this case because we are adding one character lists at a time, the concat operation takes 1 step. Since the loop iterates n times, the algorithm will perform n steps - doing 1 step per iteration. Therefore, the algorithm's time complexity would be O(n). The algorithm's actual execution time would look something like T(n) = dn where d is the time it takes to perform the concatenation. For such a function, I would expect the following to be true: when you increase the input size by 10 times, the output (execution time) would increase by 10 times since:

(x, dx) --> (10x, 10dx) --> 10dx/dx = 10

However, when I actually test out the algorithm on real values and time the executions, this does not seem to be happening. Instead, when I increase the input size by 10 times, the output (execution time) increases by 100 times, and when I increase the input size by 100 times, the output increases by 10000 times. These outputs suggest a quadratic time function and O(n squared).

Here is my full code:

import timeit
def create_list_with_concat(n):
    l = []
    for i in range(n):
        l = l + [i]

t1 = timeit.Timer("create_list_with_concat(100)", "from __main__ import 
create_list_with_concat")
print("concat ",t1.timeit(number=1)*1000, "milliseconds")
t1 = timeit.Timer("create_list_with_concat(1000)", "from __main__ 
import create_list_with_concat")
print("concat ",t1.timeit(number=1)*1000, "milliseconds")
# OUTPUT
# concat  0.05283101927489042 milliseconds
# concat  2.8588240093085915 milliseconds

Thanks so much for the help.

Answer 1

The time complexity is not O(N)

The time complexity of the concat operation for two lists, A and B, is O(A + B). This is because you aren't adding to one list, but instead are creating a whole new list and populating it with elements from both A and B, requiring you to iterate through both.

Therefore, doing the operation l = l + [i] is O(len(l)), leaving you with N steps of doing an N operation, resulting in an overall complexity of O(N^2)

You are confusing concat with the append or extend function, which doesn't create a new list but adds to the original. If you used those functions, your time complexity would indeed be O(N)

An additional note:

The notation l = l + [i] can be confusing because intuitively it seems like [i] is simply being added to the existing l. This isn't true!

l + [i] builds a entirely new list and then has l point to that list.

On the other hand l += [i] modifies the original list and behaves like extend