Time & Space complexity [Cheat Sheet]

The efficiency of an algorithm can be measured by two parameters:

Time Complexity

Time Complexity also known as running time of an algorithm is the number of primitive operations executed on a particular input.

Space Complexity

Space Complexity is the total (extra) memory space required by the program for its execution. The space complexity of an algorithm  is the amount of memory space required to solve the computational problem.

Big-O Complexity chart [1]
Sorting Algorithms

AlgorithmTime Complexity

Space Complexity

BestAverageWorstWorst
QuicksortΩ(n log(n))Θ(n log(n))O(n2)O(log(n))
MergesortΩ(n log(n))Θ(n log(n))O(n log(n))O(n)
TimsortΩ(n)Θ(n log(n))O(n log(n))O(n)
HeapsortΩ(n log(n))Θ(n log(n))O(n log(n))O(1)
Bubble SortΩ(n)Θ(n2)O(n2)O(1)
Insertion SortΩ(n)Θ(n2)O(n2)O(1)
Selection SortΩ(n2)Θ(n2)O(n2)O(1)
Tree SortΩ(n log(n))Θ(n log(n))O(n2)O(n)
Shell SortΩ(n log(n))Θ(n(log(n))2)O(n(log(n))2)O(1)
Bucket SortΩ(n+k)Θ(n+k)O(n2)O(n)
Radix SortΩ(nk)Θ(nk)O(nk)O(n+k)
Counting SortΩ(n+k)Θ(n+k)O(n+k)O(k)
CubesortΩ(n)Θ(n log(n))O(n log(n))O(n)
Data Structure Operations

Data Structure


Time Complexity



Space Complexity

      Average



Worst



Worst

AccessSearchInsertionDeletionAccessSearchInsertionDeletion
ArrayΘ(1)Θ(n)Θ(n)Θ(n)O(1)O(n)O(n)O(n)O(n)
StackΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
QueueΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Singly-Linked ListΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Doubly-Linked ListΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Skip ListΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n log(n))
Hash TableN/AΘ(1)Θ(1)Θ(1)N/AO(n)O(n)O(n)O(n)
Binary Search TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)
Cartesian TreeN/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(n)O(n)O(n)O(n)
B-TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Red-Black TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Splay TreeN/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(log(n))O(log(n))O(log(n))O(n)
AVL TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
KD TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)

 

Graph algorithms

Algorithm       Time
Complexity

Space Complexity

Average Worst Worst
DFS (Depth-first Search) O(V + E) O(V + E) O(V)
BFS O(V + E) O(V + E) O(V)
Djiskstra (shortest path) O(V+E)*log(V)O(V+E)*log(V) O(V)
Bellman-ford (Shortest Path) O(V*E) O(V*E) O(V)
Kruskal’s minimum spanning tree O(E*logV) O(E*logV) O(|E|+|V|)
Prim’s minimum spanning tree  (using adjacency Matrix) O(V2) O(V2) O(1)

Reference:
[1] Big-O Cheatsheet

Leave a Reply

Your email address will not be published. Required fields are marked *