Big O Reference

Big O Reference of common algorithms and data structures

Introduction

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.


Sorting

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(n2) O(n2) O(1)
Insertion sort O(n) O(n2) O(n2) O(1)
Selection sort O(n2) O(n2) O(n2) 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(n2) 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(n1.25) conjectured O(n(3/2)) O(1)
Bucket sort O(n+k) O(n+k) O(n2) O(nk)
Radix sort O(nk) O(nk) O(nk) O(n+k)

Searching

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|2) O(|V|2) O(|V|)
Shortest path by Bellman-Ford Graph of |V| vertices and |E| edges O(|V||E|) O(|V||E|) O(|V|)

Common Data Structures

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

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


Graphs

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|2) O(|V|2) O(1) O(|V|2) O(1) O(1)
Incidence Matrix O(|V|⋅|E|) O(|V|⋅|E|) O(|V|⋅|E|) O(|V|⋅|E|) O(|V|⋅|E|) O(|E|)