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

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

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