3 ms·
O(n) - regardless linked structure or array backed.
by xxs 9y ago
O(n) - regardless linked structure or array backed.
- arethuza 9y agoHow is inserting an item at the head of a linked list O(n)?
- Joe-Z 9y agoIt'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.
- sherincall 9y agoEasy: 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 http://thedailywtf.com/articles/The-Speedup-Loop
- pflats 9y agoO(1) is a subset of O(n).
- GhostVII 9y agoO(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).
- deleted 9y ago[deleted]
- xxs 9y ago"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]