Complexity of creating list with concat operator in python

user_10853139 0
Viewed 1394

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.

data-structures time-complexity algorithm python
3 Answers

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

user_81121380

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.

This assumption is incorrect. If you write:

l + [i]

you construct a new list, this list will have m+1 elements, with m the number of elements in l, given a list is implemented like an array, we know that constructing such list will take O(m) time. We then assign the new list to l.

So that means that the total number of steps is:

 n
---
\              2
/    O(m) = O(n )
---
m=0

so the time complexity is O(n2).

You can however boost performance, by using l += [i], or even faster l.append(i), where the amortize cost is, for both l += [i] and l.append(i) O(1), so then the algorithm is O(n), the l.append(i) will however likely be a bit faster because we save on constructing a new list, etc.

user_675790 
>>> spam = []
>>> eggs = spam
>>> spam += [1]
>>> eggs
[1]
>>> spam = []
>>> eggs = spam
>>> spam = spam + [1]
>>> eggs
[]

There's a difference in complexity between mutating a list and making a new one.

user_43814870
Related