O(n) - regardless linked structure or array backed.

How is inserting an item at the head of a linked list O(n)?

Easy:

    insert(list, node):
        node.next = list.head;
        list.head = node;
        sleep(list.count++);

Remove the `sleep` in second version, and quote significant speedup. See also http://thedailywtf.com/articles/The-Speedup-Loop

It's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's O(n).

In this case it's the worst-case performance.

Who said you insert at different locations?

Nobody. But who said you insert at the head? And who said the whole thing is list-backed? Insert is just insert--not a lot to work with there.

Performance complexity is spoken to general cases and averages unless indicated otherwise.

"insert" does not stipulate prepend or append. The latter two operations are O(1) both for linked and array backed [amortized O(1) for array backed and actually faster due to high constant costs of allocating/releasing/iterating linked structures]

O(n) means it takes less than or equal to linear time to preform the operation. So if an operation is O(1), it is also O(n).

O(1) is a subset of O(n).

Depends what you mean by insert, list and array.

there's no "time complexity" associated with inserting an item to an abstract linked list. The answer varies with implementation. Any answer <= O(n) could be correct.

"Linked list" usually refers to a very specific structure (regardless of language, or whether it is implemented as pointers or arrays or whatever) - one in which to find the middle element you have to traverse at least half the list.

Singly linked list or doubly linked lists are still considered linked lists. Skip lists, even though they technically are lists of linked items, are not generally considered a "linked list" data structure.

Even ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?

But average case or worst case are in the middle (for a doubly linked list) or the end (a singly linked list without a tail pointer).

There's no "worse case" for insertion if the api just says list.insert(item).

The half-trollish point being that nothing is "obvious". Indeed, list insertion is O(1) in popular programming languages s.a python or JS.