Editing Best, worst and average case (section)

== Examples ==
=== Sorting algorithms ===
{{see also|Sorting algorithm#Comparison of algorithms}}
{| class="wikitable"
|-
! Algorithm !! Data structure !! Time complexity:Best !! Time complexity:Average !! Time complexity:Worst !! Space complexity:Worst
|-
| Quick sort || Array || O(''n'' log(''n''))|| O(''n'' log(''n''))|| O(''n''<sup>2</sup>) || O(''n'')
|-
| Merge sort || Array || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(''n'')
|-
| Heap sort || Array || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(1)
|-
| Smooth sort || Array || O(''n'') || O(''n'' log(''n'')) || O(''n'' log(''n'')) || O(1)
|-
| Bubble sort || Array || O(''n'') || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(1)
|-
| Insertion sort || Array || O(''n'') || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(1)
|-
| Selection sort || Array || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(''n''<sup>2</sup>) || O(1)
|-
| Bogo sort || Array || O(''n'') || O(''n'' ''n''!) || O(∞) || O(1)
|}
[[File:Comparison computational complexity.svg|thumb|Graphs of functions commonly used in the analysis of algorithms, showing the number of operations ''N'' versus input size ''n'' for each function]]
* [[Insertion sort]] applied to a list of ''n'' elements, assumed to be all different and initially in random order. On average, half the elements in a list ''A''<sub>1</sub> ... ''A''<sub>''j''</sub> are less than element ''A''<sub>''j''+1</sub>, and half are greater. Therefore, the algorithm compares the (''j''&nbsp;+&nbsp;1)<sup>th</sup> element to be inserted on the average with half the already sorted sub-list, so ''t''<sub>''j''</sub> = ''j''/2. Working out the resulting average-case running time yields a quadratic function of the input size, just like the worst-case running time.
* [[Quicksort]] applied to a list of ''n'' elements, again assumed to be all different and initially in random order. This popular [[sorting algorithm]] has an average-case performance of O(''n''&nbsp;log(''n'')), which contributes to making it a very fast algorithm in practice. But given a worst-case input, its performance degrades to O(''n''<sup>2</sup>). Also, when implemented with the "shortest first" policy, the worst-case space complexity is instead bounded by&nbsp;O(log(''n'')).
* Heapsort has O(n) time when all elements are the same. Heapify takes O(n) time and then removing elements from the heap is O(1) time for each of the n elements. The run time grows to O(nlog(n)) if all elements must be distinct.
* [[Bogosort]] has O(n) time when the elements are sorted on the first iteration. In each iteration all elements are checked if in order. There are n! possible permutations; with a balanced random number generator, almost each permutation of the array is yielded in n! iterations. Computers have limited memory, so the generated numbers cycle; it might not be possible to reach each permutation. In the worst case this leads to O(∞) time, an infinite loop.


=== 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.