Editing Best, worst and average case (section)

=== Data structures ===
{{see also|Search data structure#Asymptotic worst-case analysis}}
{| class="wikitable"
! rowspan=2 |Data structure
! colspan=8 |Time complexity
!Space complexity
|-
! Avg: Indexing !! Avg: Search !! Avg: Insertion !! Avg: Deletion !! Worst: Indexing !! Worst: Search !! Worst: Insertion !! Worst: Deletion !! Worst
|-
| Basic [[array]] || O(1) || O(''n'') ||O(''n'') ||O(''n'') || O(1) || O(''n'') || O(''n'') || O(''n'') || O(''n'')
|-
| [[Dynamic array]] || O(1) || O(''n'') || O(''n'') ||{{sdash}} || O(1) || O(''n'') || O(''n'') ||{{sdash}} || O(''n'')
|-
| [[Stack (abstract data type)|Stack]] || O(''n'') || O(''n'') || O(1) || O(1) || O(''n'') || O(''n'') || O(1) || O(1) || O(''n'')
|-
| [[Queue (abstract data type)|Queue]] || O(''n'') || O(''n'') || O(1) || O(1) || O(''n'') || O(''n'') || O(1) || O(1) || O(''n'')
|- 
| [[Singly linked list]] || O(''n'') || O(''n'') || O(1) ||  O(1) || O(''n'') || O(''n'') || O(1) || O(1) || O(''n'')
|-
| [[Doubly linked list]] || O(''n'') || O(''n'') || O(1) ||  O(1) || O(''n'') || O(''n'') || O(1) || O(1) || O(''n'')
|-
| [[Skip list]] || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'') || O(''n'') || O(''n'') || O(''n'') || O(''n''log (''n'')) 
|-
| [[Hash table]] ||{{sdash}}|| O(1) || O(1) || O(1) ||{{sdash}} || O(''n'') || O(''n'') || O(''n'') || O(''n'')
|-
| [[Binary search tree]] || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'') || O(''n'') || O(''n'') || O(''n'') || O(''n'')
|-
| [[Cartesian tree]] ||{{sdash}} || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) ||{{sdash}} || O(''n'') || O(''n'') || O(''n'') || O(''n'')
|-
| [[B-tree]] || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'')
|-
| [[Red–black tree]] || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'')
|-
| [[Splay tree]] ||{{sdash}} || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || {{sdash}} || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'')
|-
| [[AVL tree]] || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'')
|-
| [[K-d tree]] || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(log (''n'')) || O(''n'') || O(''n'') || O(''n'') || O(''n'') ||  O(''n'')
|}
* [[Linear search]] on a list of ''n'' elements. In the absolute worst case, the search must visit every element once. This happens when the value being searched for is either the last element in the list, or is not in the list. However, on average, assuming the value searched for is in the list and each list element is equally likely to be the value searched for, the search visits only ''n''/2 elements.