3 ms·
It's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's O(n).
by Joe-Z 9y ago
It's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's O(n).
- poikniok 9y agoWho said you insert at different locations?
- abalashov 9y agoNobody. 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.
- chaosite 9y agoIn this case it's the worst-case performance.