It's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's 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

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

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

"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]

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