You are creating a new list object each time by concatenating. This requires copying all elements from the old list into a new one, plus one extra. So yes, using l = l + [i] is an O(N) algorithm, not O(1).

At the very least, don't use + concatenation; use += augmented concatenation, which is the same thing as list.extend() with a re-assignment to the same reference:

def test3():
    l = []
    for i in range(1000):
        l += [i]  # or use l.extend([i])
    return l

This produces:

>>> print timeit.repeat(stmt=test1, number=100, repeat=2)
[0.1333179473876953, 0.12804388999938965]
>>> print timeit.repeat(stmt=test2, number=100, repeat=2)
[0.01052403450012207, 0.007989168167114258]
>>> print timeit.repeat(stmt=test3, number=100, repeat=2)
[0.013209104537963867, 0.011193037033081055]

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

When you concatenate the two lists with A + B, you create a completely new list in memory. This means your guess is correct: the complexity is O(n + m) (where n and m are the lengths of the lists) since Python has to walk both lists in turn to build the new list.

You can see this happening in the list_concat function in the source code for Python lists:

static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
/* ...code snipped... */
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {     /* walking list a */
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {     /* walking list b */
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
/* ...code snipped... */

If you don't need a new list in memory, it's often a good idea to take advantage of the fact that lists are mutable (and this is where Python is smart). Using A.extend(B) is O(m) in complexity meaning that you avoid the overhead of copying list a.

The complexity of various list operations are listed here on the Python wiki.

In CPython, the standard implementation of Python, there's an implementation detail that makes this usually O(n), implemented in the code the bytecode evaluation loop calls for + or += with two string operands. If Python detects that the left argument has no other references, it calls realloc to attempt to avoid a copy by resizing the string in place. This is not something you should ever rely on, because it's an implementation detail and because if realloc ends up needing to move the string frequently, performance degrades to O(n^2) anyway.

Without the weird implementation detail, the algorithm is O(n^2) due to the quadratic amount of copying involved. Code like this would only make sense in a language with mutable strings, like C++, and even in C++ you'd want to use +=.

Referencing my comment again, "appending" a list to a list is still O(1), you are just adding the reference to the list, "extending" a list of size m is going to cost you O(m), since it has to traverse the other list of size m to append every single element.

seq = [1, 2, 3]
new_seq = [4, 5, 6]

# Appending is O(1)
seq.append(new_seq)
print(seq) # [1, 2, 3, [4, 5, 6]]

seq = [1, 2, 3]
new_seq = [4, 5, 6]

# Extending is O(m), m = len(new_seq)
seq.extend(new_seq)

print(seq) #[1, 2, 3, 4, 5, 6]


list_ = []
list_.append([_ for _ in range(0,n)])

You take O(n) time to create the list [_ for _ in range(0,n)] then O(1) time to add the reference of this list to your list_. O(n) in total for the line list_.append([_ for _ in range(0,n)]).

In a performance oriented code, it is not a good idea to add 2 strings together, it is preferable to use a "".join(_items2join_) instead. (I found some benchmarks there : http://www.skymind.com/~ocrow/python_string/)