| bogo |
already sorted: $T(n) = n - 1 = O(n)$ |
$T(n)$ is unbounded |
Shuffle until sorted, O(n) |
| bubble |
already sorted: $T(n) = n - 1 = O(n)$ |
reverse sorted: $T(n) = n(n-1) = O(n^2)$ |
Adjacent values are swapped until the end is reached, O(n^2) |
| insertion |
already sorted: $T(n) = n - 1 = O(n)$ |
reverse sorted: $T(n) = \sum_{1}^{n-1} i = \frac{n^2-n}{2} = O(n^2)$ |
Smaller values are shifted forwards so that a larger value can move up in the data structure, O(n^2) |
| selection |
$O(n^2)$ |
$O(n^2)$ |
Smallest value is selected and moved to the front, O(n^2) |