Content deleted Content added
m Reverted edits by 142.245.59.16 (talk) to last revision by 128.187.97.18 (HG) |
Inserting into a sorted linked list is O(log n) because you can search for the index using a binary-search. |
||
Line 67:
|-
| Sorted linked list
| O(log n)
| O(1)<sup>*</sup>
| O(''n'')
Line 94:
| O(''n'')
|}
<small> * The cost to add or delete an element into a known ___location in the list (i.e. if you have an iterator to the ___location) is O(1). If you don't know the ___location, then you need to traverse the list to the ___location of deletion/insertion using binary-search, which takes O(log ''n'') time.</small>
<small> ** The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>
| |||