4 ms·
What is the runtime complexity for inserting an item into a list or array?
by brookside 9y ago
What is the runtime complexity for inserting an item into a list or array?
- xxs 9y agoO(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]
- avip 9y agothere's no "time complexity" associated with inserting an item to an abstract linked list. The answer varies with implementation. Any answer <= O(n) could be correct.
- beagle3 9y ago"Linked list" usually refers to a very specific structure (regardless of language, or whether it is implemented as pointers or arrays or whatever) - one in which to find the middle element you have to traverse at least half the list. Singly linked list or doubly linked lists are still considered linked lists. Skip lists, even though they technically are lists of linked items, are not generally considered a "linked list" data structure.
- avip 9y agoEven ignoring "implementation details", insertion at head/tail would be O(1). Why would you traverse the list to insert an item?
- beagle3 9y agoBut average case or worst case are in the middle (for a doubly linked list) or the end (a singly linked list without a tail pointer).
- avip 9y agoThere's no "worse case" for insertion if the api just says list.insert(item). The half-trollish point being that nothing is "obvious". Indeed, list insertion is O(1) in popular programming languages s.a python or JS.
- dean177 9y agoDepends what you mean by insert, list and array.