Searching
| Algorithm | Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|---|
| Average | Worst | Worst | ||||
| Graph of |V| vertices and |E| edges | - | O(|E| + |V|) | O(|V|) | |||
| Graph of |V| vertices and |E| edges | - | O(|E| + |V|) | O(|V|) | |||
| Sorted array of n elements | O(log(n)) | O(log(n)) | O(1) | |||
| Array | O(n) | O(n) | O(1) | |||
| Graph with |V| vertices and |E| edges | O((|V| + |E|) log |V|) | O((|V| + |E|) log |V|) | O(|V|) | |||
| Graph with |V| vertices and |E| edges | O(|V|^2) | O(|V|^2) | O(|V|) | |||
| Graph with |V| vertices and |E| edges | O(|V||E|) | O(|V||E|) | O(|V|) | |||
Sorting
| Algorithm | Data Structure | Time Complexity | Worst Case Auxiliary Space Complexity | ||||
|---|---|---|---|---|---|---|---|
| Best | Average | Worst | Worst | ||||
| Array | O(n log(n)) | O(n log(n)) | O(n^2) | O(n) | |||
| Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) | |||
| Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | |||
| Array | O(n) | O(n^2) | O(n^2) | O(1) | |||
| Array | O(n) | O(n^2) | O(n^2) | O(1) | |||
| Array | O(n^2) | O(n^2) | O(n^2) | O(1) | |||
| Array | O(n+k) | O(n+k) | O(n^2) | O(nk) | |||
| Array | O(nk) | O(nk) | O(nk) | O(n+k) | |||
Data Structures
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Indexing | Search | Insertion | Deletion | Indexing | Search | Insertion | Deletion | ||
O(1) | O(n) | - | - | O(1) | O(n) | - | - | O(n) | |
O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) | |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) | |
- | O(1) | O(1) | O(1) | - | O(n) | O(n) | O(n) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) | |
- | O(log(n)) | O(log(n)) | O(log(n)) | - | O(n) | O(n) | O(n) | O(n) | |
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) | |
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) | |
- | O(log(n)) | O(log(n)) | O(log(n)) | - | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | |
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) | |
Heaps
| Heaps | Time Complexity | |||||||
|---|---|---|---|---|---|---|---|---|
| Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge | ||
- | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) | ||
- | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | ||
O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) | ||
- | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | ||
- | O(1) | O(log(n))* | O(1)* | O(1) | O(log(n))* | O(1) | ||
Graphs
| Node / Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
|---|---|---|---|---|---|---|
O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) | |
O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) | |
O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) | |
O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|E|) |
Notation for asymptotic growth
| letter | bound | growth |
|---|---|---|
| (theta) Θ | upper and lower, tight | equal |
| (big-oh) O | upper, tightness unknown | less than or equal |
| (small-oh) o | upper, not tight | less than |
| (big omega) Ω | lower, tightness unknown | greater than or equal |
| (small omega) ω | lower, not tight | greater than |
[1] Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n).
[2] f(x)=Θ(g(n)) means f (the running time of the algorithm) grows exactly like g when n (input size) gets larger. In other words, the growth rate of f(x) is asymptotically proportional to g(n).
[3] Same thing. Here the growth rate is no faster than g(n). big-oh is the most useful because represents the worst-case behavior.
In short, if algorithm is __ then its performance is __
| algorithm | performance |
|---|---|
| o(n) | < n |
| O(n) | ≤ n |
| Θ(n) | = n |
| Ω(n) | ≥ n |
| ω(n) | > n |
Big-O Complexity Chart
This interactive chart, created by our friends over at , shows the number of operations (y axis) required to obtain a result as the number of elements (x axis) increase. O(n!) is the worst complexity which requires 720 operations for just 6 elements, while O(1) is the best complexity, which only requires a constant number of operations for any number of elements.
MeteorCharts Line Chart Description
The title of the chart is "Big-O Complexity Chart". The x axis begins at "0" and ends at "100" from left to right. The y axis begins at "0k" and ends at "1k" from bottom to top. There are 7 series lines. The line titled "O(n!)" begins at "0k" and rises to "5k". The line titled "O(2^n)" begins at "0k" and rises to "4.1k". The line titled "O(n^2)" begins at "0k" and rises to "5.9k". The line titled "O(n log(n))" begins at "0k" and rises to "0.5k". The line titled "O(n)" begins at "0k" and rises to "0.1k". The line titled "O(log(n))" begins at "0k" and rises to "0k". The line titled "O(1)" begins at "0k" and rises to "0k".
Reference: