Complexity of creating list with concat operator in python

python time complexity
string slicing python time complexity

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.


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

TimeComplexity, This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in Internally, a list is represented as an array; the largest costs come from growing append. O(1). O(1). appendleft. O(1). O(1). pop. O(1). O(1). popleft To perform set operations like s-t, both s and t need to be sets. Complexity of creating list with concat operator in python 4


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.

Complexity of Python Operations, The operations are organized by increasing complexity class Lists: Complexity O(1) | Append | l.append(5) | O(1) | mostly: ICS-46 covers details Pop | l.pop() Log N) - for fast Python sorting because sorted will create a list of all the values in​  The following are code examples for showing how to use operator.concat().They are from open source Python projects. You can vote up the examples you like or vote down the ones you don't like.


>>> 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.

Python, Polynomial Time Approximation Scheme · A Time Complexity Question Let's see how to concatenate two lists using different methods in Python. The most conventional method to perform the list concatenation, the use of “+” operator can In this case, a new list is created, but this method is a one liner alternative to  How to concatenate strings in Python is explained below with the sample code.Concatenate multiple strings: + operator, += operator Concatenate strings and numbers: + operator, += operator, str(), format() Concatenate a list of strings into one string: join() Concatenate a list of numbers into one st


Performance of Python Types, Lists. The designers of the Python list data type had many choices to make during to do this: you can use the append method or the concatenation operator ( + ). As of this writing, the Python wiki has a nice time complexity page that can be  [a] + [b] produces a new list with the result [a, b]. [a].extend([b]) produces the same result, but in-place of the first list. The function actually does not return anything at all.


Time complexity of array/list operations [Java, Python] · YourBasic, The time to append an element is linear in the worst case, since it involves allocating new memory and copying each element. However, if we expand the array by  Python String Concatenation In Python, Strings are arrays of bytes representing Unicode characters. However, Python does not have a character data type, a single character is simply a string with a length of 1.


Data Structures and Algorithms with Python, the programmer pass in a list or sequence to put in the list initially. The complexity of creating a PyList object is O(1) if no value is passed to the constructor and So, to implement the get item and set item operations on PyList​, we'll use the get and set 10 4.2.4 PyList Concatenate 1 def __add__(self,other​): 2 result = Fig. list The Average Case assumes parameters generated uniformly at random. Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move).