From the docs:

list.remove(x) Remove the first item from the list whose value is x. It is an error if there is no such item.

Without going into the details of the implementation, the item to remove can be anywhere in the list. A linear scan time is necessary in order to find the item before it can be removed. Once you find the index of the item to remove, you need to shift all the elements down by one index. In any case there's index amount of traversal and size - index amount of shifting involved. Therefore the removal time is equivalent to traversing the entire list: O(n).

You can find the source here: https://hg.python.org/cpython/file/tip/Objects/listobject.c#l2197 (also look for list_ass_slice(..)).

However, a set is different. It uses the hash value of the object being stored to locate it in its buckets. On an average, locating of objects using hash value is almost constant time. Note that it might not always be constant time where there's hash collision and a further search is required. But assuming a good hash function, it usually is.

UPDATE: I must thank Stefan Pochmann for pointing out the mistake.

The pointer to where the list really starts must be retained for the purpose of freeing the memory appropriately.

Indeed, remove(0) could be made faster by having a second pointer which is increased in this case. And if an .add(0, x) happens afterwards, this could be made faster by decrementing this "data start timer" as long as it is bigger than the "memory start timer".

But all other operations, i. e. insertions and deletions to other indexes, would still be O(n), so that wouldn't change much.

Just know what your operations will be and thus which data structure to pick.

I decided to turn my set of comments into a proper answer.

First off, let's clarify what's happening when you do:

>>> l = [i for i in range(100000000)]

Here three things are happening:

1. 100000000 int objects are being created. Creating an object in CPython requires allocating memory and placing content into that memory, and this takes time.
2. You are running a loop. This affects performances considerably: [i for i in range(...)] is much slower than list(range(...)).
3. The large list is being created on the fly.

Reading your question, it seems that you are considering only the last point, ignoring the others. Therefore, your timings are inaccurate: creating a large list does not take 3 seconds, it takes a fraction of those 3 seconds.

How large is this fraction is an interesting question, which is difficult to answer using only Python code, but still we can try. Specifically, I'd try with the following statement:

>>> [None] * 100000000

Here CPython does not have to create a large amount of objects (there's only None), does not have to run loops and can allocate the memory for the list once (because it knows the size in advance).

Timings are self-explanatory:

$ python3 -m timeit "list(range(100000000))"
10 loops, best of 3: 2.26 sec per loop
$ python3 -m timeit "[None] * 100000000"
10 loops, best of 3: 375 msec per loop

Now, back to your question: how about item deletion?

$ python3 -m timeit --setup "l = [None] * 100000000" "del l[0]"
10 loops, best of 3: 89 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 4]"
10 loops, best of 3: 66.5 msec per loop
$ python3 -m timeit --setup "l = [None] * 100000000" "del l[100000000 // 2]"
10 loops, best of 3: 45.3 msec per loop

These numbers tell us something important. Note that 2 × 45.3 ≈ 89. Also 66.5 × 4 / 3 ≈ 89.

These numbers are telling exactly what linear complexity is about. If a function has time complexity kn (which is O(n)), it means that if we double the input, we double time; if we increase the input size by 4/3, the time increases by 4/3.

And this is what's happening here. In CPython, our list of 100000000 items is a contiguous memory area containing pointers to Python objects:

l = |ptr0|ptr1|ptr2|...|ptr99999999|

When we run del l[0] we are moving ptr1 from right to left, overwriting ptr0. The same for other elements:

l = |ptr0|ptr1|ptr2|...|ptr99999999|
     ^^^^
         ` item to delete

l = |ptr1|ptr2|...|ptr99999999|

Therefore, when we run del l[0] we have to move 99999998 pointers to the left. This is different from del l[100000000 // 2], which requires moving only half the pointers (the pointers on the first half don't need to be moved). "Moving half the pointers" equals "performing half of the operations" which roughly mean "running in half the time" (this is not always true, but timings say that this is true in this case).

Actually, you don't have to swap; just copy the end element to the desired deletion position -- don't bother with the converse assignment -- and pop the last (now redundant) element. For removing element n,

my_list[n] = my_list.pop()

will do it in one line.

Yes, it is O(1) to pop the last element of a Python list, and O(N) to pop an arbitrary element (since the whole rest of the list has to be shifted).

Here's a great article on how Python lists are stored and manipulated: An Introduction to Python Lists.

As you correctly noticed, the CPython implementation of list.clear is O(n). The code iterates over the elements in order to decrease the reference count of each one, without a way to avoid it. There is no doubt that it is an O(n) operation and, given a large enough list, you can measure the time spent in clear() as function of list size:

import time

for size in 1_000_000, 10_000_000, 100_000_000, 1_000_000_000:
    l = [None] * size
    t0 = time.time()
    l.clear()
    t1 = time.time()
    print(size, t1 - t0)

The output shows linear complexity; on my system with Python 3.7 it prints the following:

1000000 0.0023756027221679688
10000000 0.02452826499938965
100000000 0.23625731468200684
1000000000 2.31496524810791

The time per element is of course tiny because the loop is coded in C and each iteration does very little work. But, as the above measurement shows, even a miniscule per-element factor eventually adds up. Small per-element constant is not the reason to ignore the cost of an operation, or the same would apply to the loop that shifts the list elements in l.insert(0, ...), which is also very efficient - and yet few would claim insertion at the beginning to be O(1). (And clear potentially does more work because a decref will run an arbitrary chain of destructors for an object whose reference count actually reaches zero.)

On a philosophical level, one could argue that costs of memory management should be ignored when assessing complexity because otherwise it would be impossible to analyze anything with certainty, as any operation could trigger a GC. This argument has merit; GC does come occasionally and unpredictably, and its cost can be considered amortized across all allocations. In a similar vein complexity analysis tends to ignore the complexity of malloc because the parameters it depends on (like memory fragmentation) are typically not directly related to allocation size or even to the number of already allocated blocks. However, in case of list.clear there is only one allocated block, no GC is triggered, and the code is still visiting each and every list element. Even with the assumption of O(1) malloc and amortized O(1) GC, list.clear still takes the time proportional to the number of elements in the list.

The article linked from the question is about Python the language and doesn't mention a particular implementation. Python implementations that don't use reference counting, such as Jython or PyPy, are likely to have true O(1) list.clear, and for them the claim from the article would be entirely correct. So, when explaining the Python list on a conceptual level, it is not wrong to say that clearing the list is O(1) - after all, all the object references are in a contiguous array, and you free it only once. This is the point your blog post probably should make, and that is what the linked article is trying to say. Taking the cost of reference counting into account too early might confuse your readers and give them completely wrong ideas about Python's lists (e.g. they could imagine that they are implemented as linked lists).

Finally, at some point one must accept that memory management strategy does change complexity of some operations. For example, destroying a linked list in C++ is O(n) from the perspective of the caller; discarding it in Java or Go would be O(1). And not in the trivial sense of a garbage-collected language just postponing the same work for later - it is quite possible that a moving collector will only traverse reachable objects and will indeed never visit the elements of the discarded linked list. Reference counting makes discarding large containers algorithmically similar to manual collection, and GC can remove that. While CPython's list.clear has to touch every element to avoid a memory leak, it is quite possible that PyPy's garbage collector never needs to do anything of the sort, and thus has a true O(1) list.clear.