Content deleted Content added
m Fixed a typing mistake (changed "ietms" into "items") |
→Asymptotic worst-case analysis: Updated Linked Lists to reflect proper time cost |
||
Line 65:
|-
| Sorted linked list
| O(1)/O(''n'')<sup>*</sup>
| O(1)/O(''n'')<sup>*</sup>
| O(''n'')
| O(1)
Line 92:
| O(''n'')
|}<small> † The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>
<small> * The cost to add or delete an element into a known ___location in the list is O(1), but only after the list has been traversed to the ___location of deletion/insertion, which takes O(''n'') time.</small>
This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs. Also two or more data structures can be combined to obtain lower costs.
| |||