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

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

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.