http://leepoint.net/notes-java/algorithms/big-oh/bigoh.htmlHere is a table of typical cases, showing how many "operations" would be performed for various values of N. Logarithms to base 2 (as used here) are proportional to logarithms in other base, so this doesn't affect the big-oh formula.
| constant | logarithmic | linear | | quadratic | cubic |
|---|
| n | O(1) | O(log N) | O(N) | O(N log N) | O(N2) | O(N3) |
|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |
| 1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 | 1016 |
Searching
Here is a table of typical cases.
| Type of Search | Big-Oh | Comments |
|---|
| Linear search array/ArrayList/LinkedList | O(N) | |
| Binary search sorted array/ArrayList | O(log N) | Requires sorted data. |
| Search balanced tree | O(log N) | |
| Search hash table | O(1) | |
| Algorithm | array
ArrayList | LinkedList |
|---|
| access front | O(1) | O(1) |
| access back | O(1) | O(1) |
| access middle | O(1) | O(N) |
| insert at front | O(N) | O(1) |
| insert at back | O(1) | O(1) |
| insert in middle | O(N) | O(1) |
Sorting arrays/ArrayLists
Some sorting algorithms show variability in their Big-Oh performance. It is therefore interesting to look at their best, worst, and average performance. For this description "average" is applied to uniformly distributed values. The distribution of real values for any given application may be important in selecting a particular algorithm.
| Type of Sort | Best | Worst | Average | Comments |
|---|
| BubbleSort | O(N) | O(N2) | O(N2) | Not a good sort, except with ideal data. |
| Selection sort | O(N2) | O(N2) | O(N2) | Perhaps best of O(N2) sorts |
| QuickSort | O(N log N) | O(N2) | O(N log N) | Good, but it worst case is O(N2) |
| HeapSort | O(N log N) | O(N log N) | O(N log N) | Typically slower than QuickSort, but worst case is much better. |
