Big O Algorithm Complexity Sheet
Complexities!
Good Fair Poor
Searching
Algorithm
Data Structure
Time Complexity
Depth First Search
(DFS)
Graph of |V| vertices and |E| edges Graph of |V| vertices and |E| edges Sorted array of n elements Array
-
O(|E| + |V|)
O(|V|)
-
O(|E| + |V|)
O(|V|)
O(log(n))
O(log(n))
O(1)
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|)
Average
Breadth First
Search (BFS)
Binary search
Linear (Brute
Force)
Shortest path by
Dijkstra,
using a Min-heap as priority queue
Shortest path by
Dijkstra,
using an unsorted array as priority queue Shortest path by
Bellman-Ford
Worst
Space
Complexity
Worst
Sorting
Algorithm
Data
Structure
Time Complexity
Best
Quicksort
Array
Mergesort
Array
Heapsort
Array
Bubble Sort
Insertion
Sort
Select Sort
Bucket Sort
Radix Sort
Array
Array
O(n log(n)) O(n log(n)) O(n log(n)) O(n)
O(n)
Array
Array
Array
O(n^2)
O(n+k)
O(nk)
Average
Worst
Worst Case Auxiliary
Space Complexity
Worst
O(n log(n)) O(n log(n)) O(n log(n)) O(n^2)
O(n^2)
O(n^2)
O(n)
O(n log(n)) O(n log(n)) O(n^2)
O(n^2)
O(n)
O(n^2)
O(n+k)
O(nk)
O(n^2)
O(n^2)
O(nk)
O(1)
O(nk)
O(n+k)
O(1)
O(1)
O(1)
Data Structures
Data Structure
Time Complexity
Indexing
Average
Search
Insertion
Deletion
Basic Array
Dynamic Array
Singly-Linked
List
Doubly-Linked
List
Skip List
O(1)
O(1)
O(n)
O(n)
O(n)
O(n)
-
-
O(n)
O(1)
O(n)
O(n)
O(log(n))
Hash Table
Binary Search
Tree
Cartresian Tree
B-Tree
Red-Black Tree
Splay Tree
AVL Tree
Indexing
Space
Complex
ity
Worst
Worst
Search
Insertion
Deletion
O(n)
O(n)
O(n)
-
-
O(n)
O(1)
O(1)
O(1)
O(n)
O(n)
O(1)
O(n)
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(n)
O(n)
O(n)
O(n)
O(log(n))
O(1)
O(log(n))
O(1)
O(log(n))
O(1)
O(log(n))
O(n)
O(n)
O(n)
O(n)
Good Fair Poor
Searching
Algorithm
Data Structure
Time Complexity
Depth First Search
(DFS)
Graph of |V| vertices and |E| edges Graph of |V| vertices and |E| edges Sorted array of n elements Array
-
O(|E| + |V|)
O(|V|)
-
O(|E| + |V|)
O(|V|)
O(log(n))
O(log(n))
O(1)
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|)
Average
Breadth First
Search (BFS)
Binary search
Linear (Brute
Force)
Shortest path by
Dijkstra,
using a Min-heap as priority queue
Shortest path by
Dijkstra,
using an unsorted array as priority queue Shortest path by
Bellman-Ford
Worst
Space
Complexity
Worst
Sorting
Algorithm
Data
Structure
Time Complexity
Best
Quicksort
Array
Mergesort
Array
Heapsort
Array
Bubble Sort
Insertion
Sort
Select Sort
Bucket Sort
Radix Sort
Array
Array
O(n log(n)) O(n log(n)) O(n log(n)) O(n)
O(n)
Array
Array
Array
O(n^2)
O(n+k)
O(nk)
Average
Worst
Worst Case Auxiliary
Space Complexity
Worst
O(n log(n)) O(n log(n)) O(n log(n)) O(n^2)
O(n^2)
O(n^2)
O(n)
O(n log(n)) O(n log(n)) O(n^2)
O(n^2)
O(n)
O(n^2)
O(n+k)
O(nk)
O(n^2)
O(n^2)
O(nk)
O(1)
O(nk)
O(n+k)
O(1)
O(1)
O(1)
Data Structures
Data Structure
Time Complexity
Indexing
Average
Search
Insertion
Deletion
Basic Array
Dynamic Array
Singly-Linked
List
Doubly-Linked
List
Skip List
O(1)
O(1)
O(n)
O(n)
O(n)
O(n)
-
-
O(n)
O(1)
O(n)
O(n)
O(log(n))
Hash Table
Binary Search
Tree
Cartresian Tree
B-Tree
Red-Black Tree
Splay Tree
AVL Tree
Indexing
Space
Complex
ity
Worst
Worst
Search
Insertion
Deletion
O(n)
O(n)
O(n)
-
-
O(n)
O(1)
O(1)
O(1)
O(n)
O(n)
O(1)
O(n)
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(n)
O(n)
O(n)
O(n)
O(log(n))
O(1)
O(log(n))
O(1)
O(log(n))
O(1)
O(log(n))
O(n)
O(n)
O(n)
O(n)