Big O Reference of common algorithms and data structures

- Introduction
- Algorithms
- Sorting
- Searching
- Data Structures
- Common Data Structures
- Heaps
- Graphs

This site summarizes the complexities in terms of space and time (Big O) of the most important algorithms and operations in common data structures. It is 100% open-source so you can edit the content with a pull request, with no ads and has a friendly printable version. If you have any comment please create an issue on Github. To know more about the project and see the credits take a look at the readme file.

Very important and useful type of algorithms for many common problems nowadays, Finder, iTunes, Excel and many more programs use some kind of sorting algorithm.

Algorithm | Time | Auxiliary Space | ||
---|---|---|---|---|

Best | Average | Worst | Worst | |

Bubble sort | `O(n)` |
`O(n` |
`O(n` |
`O(1)` |

Insertion sort | `O(n)` |
`O(n` |
`O(n` |
`O(1)` |

Selection sort | `O(n` |
`O(n` |
`O(n` |
`O(1)` |

Mergesort | `O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(n)` |

Quicksort | `O(n log(n))` |
`O(n log(n))` |
`O(n` |
`O(log(n))` |

Heapsort | `O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(1)` |

Shell Sort`(h=2^k-1)` |
`O(n log(n))` |
`O(n` conjectured |
`O(n` |
`O(1)` |

Bucket sort | `O(n+k)` |
`O(n+k)` |
`O(n` |
`O(nk)` |

Radix sort | `O(nk)` |
`O(nk)` |
`O(nk)` |
`O(n+k)` |

Searching efficiently is crucial for many operations in different parts of the software we use on a daily basis.

Algorithm | Data Structure | Time | Space | |
---|---|---|---|---|

Average | Worst | Worst | ||

Depth First Search (DFS) | Graph of |V| vertices and |E| edges | `-` |
`O(|E| + |V|)` |
`O(|V|)` |

Breadth First Search (BFS) | Graph of |V| vertices and |E| edges | `-` |
`O(|E| + |V|)` |
`O(|V|)` |

Binary Search | Sorted array of n elements | `O(log(n))` |
`O(log(n))` |
`O(1)` |

Linear (Brute force) | Array of n elements | `O(n)` |
`O(n)` |
`O(1)` |

Shortest path by Dijkstra, Min-heap as priority queue |
Graph of |V| vertices and |E| edges | `O((|V|+|E|) log|V|)` |
`O((|V|+|E|) log|V|)` |
`O(|V|)` |

Shortest path by Dijkstra, unsorted array as priority queue |
Graph of |V| vertices and |E| edges | `O(|V|` |
`O(|V|` |
`O(|V|)` |

Shortest path by Bellman-Ford | Graph of |V| vertices and |E| edges | `O(|V||E|)` |
`O(|V||E|)` |
`O(|V|)` |

Data structures are the key in some of the most used algorithms and a good data structure is sometimes the way to achieve a very efficient and elegant solution.

Data Structure | Time | |||||||
---|---|---|---|---|---|---|---|---|

Average | Worst | |||||||

Indexing | Search | Insertion | Deletion | Indexing | Search | Insertion | Deletion | |

Basic Array | `O(1)` |
`O(n)` |
`-` |
`-` |
`O(1)` |
`O(n)` |
`-` |
`-` |

Dynamic Array | `O(1)` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(n)` |
`O(n)` |
`O(n)` |

Single-Linked List | `O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |

Double-Linked List | `O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |

Skip List* | `O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`O(n)` |
`O(n)` |
`O(n)` |
`O(n)` |

Hash Table | `-` |
`O(1)` |
`O(1)` |
`O(1)` |
`-` |
`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)` |

Ternary Search Tree | `-` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`-` |
`O(n)` |
`O(n)` |
`O(n)` |

Cartesian Tree | `-` |
`O(log(n))` |
`O(log(n))` |
`O(log(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))` |

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))` |

Splay Tree | `-` |
`O(log(n))` |
`O(log(n))` |
`O(log(n))` |
`-` |
`O(log(n))` |
`O(log(n))` |
`O(log(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))` |

Note * All have space complexity of O(n) except for Skip that has O(n log(n))

Heaps | Time | ||||||
---|---|---|---|---|---|---|---|

Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge | |

Linked List | `-` |
`O(1)` |
`O(1)` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(m+n)` |

Linked List (unsorted) | `-` |
`O(n)` |
`O(n)` |
`O(1)` |
`O(1)` |
`O(1)` |
`O(1)` |

Binary Heap | `O(n)` |
`O(1)` |
`O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(m+n)` |

Binomial Heap | `-` |
`O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |
`O(n log(n))` |

Fibonnaci Heap | `-` |
`O(1)` |
`O(log(n))*` |
`O(1)*` |
`O(1)` |
`O(log(n))*` |
`O(1)` |

Note * Amortized time

Node / Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
---|---|---|---|---|---|---|

Adjacency List | `O(|V|+|E|)` |
`O(1)` |
`O(1)` |
`O(|V|+|E|)` |
`O(|E|)` |
`O(|V|)` |

Incidence List | `O(|V|+|E|)` |
`O(1)` |
`O(1)` |
`O(|E|)` |
`O(|E|)` |
`O(|E|)` |

Adjacency Matrix | `O(|V|` |
`O(|V|` |
`O(1)` |
`O(|V|` |
`O(1)` |
`O(1)` |

Incidence Matrix | `O(|V|⋅|E|)` |
`O(|V|⋅|E|)` |
`O(|V|⋅|E|)` |
`O(|V|⋅|E|)` |
`O(|V|⋅|E|)` |
`O(|E|)` |