When measuring the efficiency of an algorithm, we usually take into account the time and space complexity. In this article, we will glimpse those factors on some sorting algorithms and data structures, also we take a look at the growth rate of those operations.
Algorithms and Data Structures Cheatsheet 11/5/20, 9:06 PM Page 2 of 10 k common logarithm such that log 10. Big O Cheat Sheet for Common Data Structures and Algorithms 3 min read on August 29, 2019 When measuring the efficiency of an algorithm, we usually take into account the time and space complexity. About: I made this website as a fun project to help me understand better: algorithms, data structures and big O notation. And also to have some practice in: Java.
This cheat sheet is one you will want to bookmark as it is part of an ebook! It primarily focuses on Algorithm and Data Structures.The area I would like you to focus is ⅓ of the way down beginning at arrays. Consider bookmarking the book(I have!) Chapter 4 deep dives into algorithms and data structures.
Big-O Complexity Chart
First, we consider the growth rate of some familiar operations, based on this chart, we can visualize the difference of an algorithm with O(1) when compared with O(n2). As the input larger and larger, the growth rate of some operations stays steady, but some grow further as a straight line, some operations in the rest part grow as exponential, quadratic, factorial.
Sorting Algorithms
In order to have a good comparison between different algorithms we can compare based on the resources it uses: how much time it needs to complete, how much memory it uses to solve a problem or how many operations it must do in order to solve the problem:
- Time efficiency: a measure of the amount of time an algorithm takes to solve a problem.
- Space efficiency: a measure of the amount of memory an algorithm needs to solve a problem.
- Complexity theory: a study of algorithm performance based on cost functions of statement counts.
| Sorting Algorithms | Space Complexity | Time Complexity | ||
| Worst case | Best case | Average case | Worst case | |
Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
| Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
| Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n log n) | O(n log n) |
| Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
| ShellSort | O(1) | O(n) | O(n log n2) | O(n log n2) |
| Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
| Tree Sort | O(n) | O(n log n) | O(n log n) | O(n2) |
| Counting Sort | O(k) | O(n + k) | O(n + k) | O(n + k) |
| Cubesort | O(n) | O(n) | O(n log n) | O(n log n) |
Data Structure Operations
In this chart, we consult some popular data structures such as Array, Binary Tree, Linked-List with 3 operations Search, Insert and Delete.
| Data Structures | Average Case | Worst Case | ||||
| Search | Insert | Delete | Search | Insert | Delete | |
| Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary SearchTree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
| Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
Growth of Functions
The order of growth of the running time of an algorithm gives a simple characterization of the algorithm’s efficiency and also allows us to compare the relative performance of alternative algorithms.
Below we have the function n f(n) with n as an input, and beside it we have some operations which take input n and return the total time to calculate some specific inputs.
| n f(n) | log n | n | n log n | n2 | 2n | n! |
|---|---|---|---|---|---|---|
| 10 | 0.003ns | 0.01ns | 0.033ns | 0.1ns | 1ns | 3.65ms |
| 20 | 0.004ns | 0.02ns | 0.086ns | 0.4ns | 1ms | 77years |
| 30 | 0.005ns | 0.03ns | 0.147ns | 0.9ns | 1sec | 8.4×1015yrs |
| 40 | 0.005ns | 0.04ns | 0.213ns | 1.6ns | 18.3min | — |
| 50 | 0.006ns | 0.05ns | 0.282ns | 2.5ns | 13days | — |
| 100 | 0.07 | 0.1ns | 0.644ns | 0.10ns | 4×1013yrs | — |
| 1,000 | 0.010ns | 1.00ns | 9.966ns | 1ms | — | — |
| 10,000 | 0.013ns | 10ns | 130ns | 100ms | — | — |
| 100,000 | 0.017ns | 0.10ms | 1.67ms | 10sec | — | — |
| 1’000,000 | 0.020ns | 1ms | 19.93ms | 16.7min | — | — |
| 10’000,000 | 0.023ns | 0.01sec | 0.23ms | 1.16days | — | — |
| 100’000,000 | 0.027ns | 0.10sec | 2.66sec | 115.7days | — | — |
| 1,000’000,000 | 0.030ns | 1sec | 29.90sec | 31.7 years | — | — |
This page sums up some important results from computer science. They are extracted from the Introduction to Algorithms (Third Edition), by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. We highly recommend it.
The following information is organized in several sections grouping definitions. Each definition points to the Introduction to Algorithms for further information using the abbreviation CLRS (from the authors’ names).
The formulæ are written using (LaTeX) and the final render of the page is done by the Javascript library MathJax (currently the simplest way to use (LaTeX) in HTML).
The current figures use images from external websites. Clicking on it will redirect you to their original webpages.
Master Theorem
CLRS: p93
Recurrence of the form: (T(n) = a T(n/b) + O(f(n)))
C++ Coding Cheat Sheet
| Case | (f(n) = O(dots)) | (T(n) = O(dots)) |
|---|---|---|
| 1 | (n^{log_b a - varepsilon}) | (n^{log_b a}) |
| 2 | (n^{log_b a}) | (log n times n^{log_b a}) |
| 3 | (n^{log_b a + varepsilon}) and (exists c, a f(n/b) leq c f(n)) | (f(n)) |
call tree; (b) defines the maximal depth of the recursive calls, (a) defines the maximal number of calls to (f) at each level, summing the complexity of each of the (O(n^{log_b a})) calls to (f), which depends on the depth, explains the cases of the master theorem (the illustraction come from the CLRS Second Edition)
Matroid
CLRS: p437
Pair ((S, mathcal I)) with:
- (S) is a finite set
- (emptyset neq mathcal I subseteq mathcal P(S)) (independent subsets)
- (forall A subseteq B in mathcal I, A in mathcal I) (heredity)
- (forall A,B in mathcal I, |A| lt |B| Rightarrow exists x in B backslash A, A cup {x} in mathcal I)(exchange)
Greedy algorithms from matroids
CLRS: p439
((S, mathcal I)) is a matroid. (w) is a weight function over (S). Greedy algorithm → choosing iteratively an element maximizing (w):
- ({x} in mathcal I) with maximum weight
- (x) is in any independent subset with maximum weight
- (mathcal I' = {B subseteq S backslash {x} : B cup {x} in mathcal I}) (subsets containing (x), ignoring (x))
- (S' = {y in S, {x,y} in mathcal I)) (restricting elements)
- iterate on ((S', mathcal I')) (also a matroid)
Heap
CLRS: p151
Sorted data structure (priority queue) Min-heap: parent is bigger than its children Max-heap: parent is bigger than its children
| Operation | Complexity |
|---|---|
| Memory use | (O(n)) |
| Insert | (O(log n)) |
| Maximum | (O(1)) |
| Extract-Max | (O(log n)) |
| Increase-Key | (O(log n)) |
Hash Table
CLRS: p256
Arbitrarily indexed table (h) is a hash function to ([1..m])
- Space:(O(m))
- Locate:(O(1 + n/m))
Note: Locate finds a location in the array where the user can read or write as usual.
Binary Search Tree (BST)
CLRS: p286
Sorted data structure (h) is the height of the tree
- Space:(O(n))
- Search:(O(h))
- Insert:(O(h))
- Delete:(O(h))
Red-Black Tree
CLRS: p308
BST maintaining (h = log n) with:
- every node is either black (“normal”) or red (to be updated);
- the root is black;
- leaves are black;
- red nodes cannot have a red parent → there are no more red nodes than black ones;
- all simple paths from the root to a leaf have the same number of black nodes, limiting (h).
B-Tree
CLRS: p484
Variant of the BST using a large fan-out (t) to reduce disk-accesses Search, insert and delete take (O(log_t n)) disk accesses and (O(t log_t n)) CPU time.
Union-find
CLRS: p568
Data structure for sets, supporting union of sets and finding the representative (m) is the number of previously run Make-Set operations. (alpha) is the Ackerman function ((alpha(m) leq 4) in practise).
- Make-Set:(O(1))
- Union:(O(1))
- Find-Set:(O(alpha(m)))
Bubblesort
CLRS: p40 (problem 2-2) Complexity:(O(n^2))
Fixing inverted adjacent values (n) times
Insertion sort
Data Structures And Algorithms Cheat Sheet 2
CLRS: p16 (correctness), p24 (complexity) Complexity:(O(n^2))
Inserting each element in a new array at the right location
Merge sort
CLRS: p29 Complexity:(O(n log n))
Divide-and-conquer (sort each half, then merge)
Heapsort
CLRS: p159 Complexity:(O(n log n))
Building a heap on the (n) elements and extracting them all
Quicksort
CLRS: p170 Complexity:(O(n log n))
Divide-and-conquer (choose a pivot, then filter lower and greater values)
{Breadth,Depth}-first search
CLRS: p594 (breadth), p603 (depth) Complexity:(O(E + V))
Listing the vertices of a graph. Breadth-first search list the siblings, then the siblings’ siblings…
Depth-first search goes as far as it can before considering siblings.
Kruskal
CLRS: p631 Complexity:(O(E log V))
Finding a minimum spanning tree Consider every edge in nondecreasing order, add to current forest if links two components. The components are handled using union-find.
Prim
CLRS: p634 Complexity:(O(E log V)) (binary heap) Complexity:(O(E + V log V)) (Fibonacci heap)
Finding a minimum spanning tree Iteratively extract closest vertex (u) and relax all edges ((u, v)). The set of vertices is handled using a priority queue.
Bellman-Ford
CLRS: p651 Complexity:(O(E V))
Finding all shortest paths from a single source Just relax every edge of the graph |V| times Detects negative weight cycles
Shortest paths from DAG
CLRS: p655 Complexity:(O(V+E)) (including sorting)
Finding all shortest paths from a single source in Directed Acyclic Graphs Consider every vertex (u) in topological order and relax all edges ((u, v))
Dijkstra
CLRS: p658 Complexity:(O(V^2 + E)) (array) Complexity:(O((E+V) log V)) (binary heap) Complexity:(O(V log V + E)) (Fibonacci heap)
Finding all shortest paths from a single source with positive weights Iteratively extract closest vertex (u) and relax all edges ((u, v)). The set of vertices is handled using a priority queue.
Floyd-Warshall
CLRS: p693 Complexity:(O(V^3))
Finding the shortest path from all vertex pairs Relaxing pair distance (|V|) times
The Path-Finding Problem