On: If companies interviewed translators the way they ...

[xxs]

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

[arethuza → xxs]

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

[sherincall → arethuza]

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

[Joe-Z → arethuza]

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

[chaosite → Joe-Z]

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

[poikniok → Joe-Z]

Who said you insert at different locations?

[abalashov → poikniok]

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.

[xxs → arethuza]

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

[GhostVII → arethuza]

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

[pflats → arethuza]

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