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.
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
DATA STRUCTURES CHEAT SHEET Python - Data Structure It is a way of organizing data that contains the items stored and their relationship to each other The areas in which Data Structures are applied:. Compiler design. Operating system. Database Management System. Statistical Analysis Package. Numerical Analysis. Graphics. Algorithms and Data Structures Cheatsheet We summarize the performance characteristics of classic algorithms and data structures for sorting, priority queues, symbol tables, and graph processing. C Data Structures and Algorithms Cheat Sheet. Basic Types of Algorithms. Data Structure Basics. Efficient Sorting Basics. Below is a poster which gives a simplified overview of Data Structures and Algorithms and contains most of the import stuff to remember (for interviews or exams). Unlike the Big-O-Cheat-Sheet's paid offering, you can download it in high resolution here for free (don't waste $14 dollars)!
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 | — | — |
I wanted a concise, comprehensive, and correct cheat sheet for a quick review for technical interviews but couldn't find a satisfactory one online, thus I created my own. Runtime refers to average runtime. A Mark-down version can be found here. Feel free to fork it, and modify it as you like. Please comment for mistakes or important concepts missed
Data Structures
1 Dynamic Array
Sequentially stored data in a continuous chunk of memory. Double current capacity whenever capacity reached. When increasing capacity, it allocates new chunk of memory and copy over the previous values to new location.
Runtime
- indexing: O(1)
- searching: O(n)
- insertion: O(n)
- push: O(n) Note: O(1) Amortized
- deletion: O(n)
2 Linked List
Most commonly refers to singly linked list. Data stored in nodes where each node has a reference to the next node. There are doubly linked list and circular linked list as well.
Runtime
- indexing: O(n)
- searching: O(n)
- insertion: O(1)
- deletion: O(1)
Stack and queue are often implemented with linked list because linked list are most performant for insertion/deletion, which are the most frequently used operations for stacks/queues.
Stack Last in First Out (LIFO)
Queue First in First Out (FIFO)
3 Hash Table (Hash Map)
A usually unordered data structure that maps keys to values. A hash (preferably unique) is computed for a given key and its value will be stored in the corresponding bins or index according to the hash. Internally the bins can be an array. Collision can happen when multiple keys are mapped to the same hash. Common resolution is to store a list/linked-list at each bin/index location (called chaining).
Runtime
- value lookup: O(1)
- insertion: O(1)
- deletion: O(1)
4 Binary Search Tree (BST)
A binary tree with extra condition that each node is greater than or equal to all nodes in left sub-tree, and smaller than or equal to all nodes in right sub-tree.
Runtime
- searching: O(log n)
- insertion: O(log n)
- deletion: O(log n)
5 Heap (Max Heap/Min Heap)
A binary tree with the condition that parent node's value is bigger/smaller than its children. So root is the maximum in a max heap and minimum in min heap. Priority queue is also referred to as heap because it's usually implemented by a heap.
Runtime
Sorting Algorithms Cheat Sheet
- min/max: O(1)
- insertion: O(log n)
- deletion: O(log n)
Algorithms
1 Sorting
Bubble Sort Iterate through entire list while comparing pairs and swap positions based on their values until all elements sorted.
- O(n^2), but fast if list is almost sorted.
Insertion Sort Iterates through unsorted list while building a sorted list. For each value encountered in unsorted list, find appropriate place in sorted list and insert it.
- O(n^2).
Merge Sort A type of divide and conquer algorithm: 1) divides the list into two equally sized sub lists 2) sort each sub list 3) merge two sorted lists into final list.
- O(n log n) - needs to divide log n times, and for each divide, it needs to go through all n items to merge, thus n times log n.
Heap Sort 1) Build a heap (min or max) from the unsorted list 2)repeatedly remove the root node from the heap and put into the sorted list.
- O(n log n) - remove root node is O(log n), and has to be repeated for each node, thus n times log n.
Quick Sort A type of divide and conquer algorithm: 1) pick an item in the unsorted list as pivot 2) divided list into 2 sub lists, one contains elements smaller than pivot while the other contains elements greater than the pivot 3) sort the sub lists, and combine the results into final list
Data Structures And Algorithms Cheat Sheet Python
- O(n log n) - need to divide O(log n) times, and after each divide, the partitioning has to go through all elements, thus overall runtime n times log n.
2 Searching
Linear SearchO(n)
Binary Search O(log n)
Breadth-First-Search (BFS) Siblings first then children. Use queue usually.
Depth-First-Search (DFS) Children first then siblings. Use stack usually.
Data Structures And Algorithms Cheat Sheet
A* Search Goal is to find the shortest path between 2 nodes in a graph. It's a best-first search. At each iteration it finds the next node to extend the path based on the criteria g(next) + h(next) where g is the distance from next node to starting node and h is the heuristic (estimated) distance of next node to final node. use a heap usually.
Computer Science Data Structures And Algorithms Cheat Sheet
3 Tree Traversals
Inorder (Left, Root, Right): useful for getting sorted list out of BST
Data Structures And Algorithms Cheat Sheet 2
Preorder (Root, Left, Right): useful for making copy of binary trees, or evaluate expression trees.
Postorder (Left, Right, Root): useful for deleting trees (because need to delete children before deleting parent)