Big-O notation is a mathematical representation used to describe the complexity of a data structure and algorithm. There are two types of Complexity :
- Time Complexity: Its measure based on steps need to follow for an algorithm.
- Space Complexity: It measures the space required to perform an algorithm and data structure.
Data Structure and Algorithm Decision
Data structure and algorithm decisions are based on the complexity of size and operations need to perform on data. Some algorithms perform better on a small set of data while others perform better for big data sets for certain operations.
These days Space Complexity is not big concerns but the main performance of an algorithm measures based on time complexity. We can make the decision to choose an algorithm based on below performance criteria with respect to Complexity.
| Complexity | Performance |
| O(1) | Excellent |
| O(log(n)) | Good |
| O(n) | Fair |
| O(n log(n)) | Bad |
| O(n^2) | Horrible |
| O(2^n) | Horrible |
| O(n!) | Horrible |
This post almost covers data structure and algorithms space and time Big-O complexities. Here you can also see time complexities for types of operations like access, search, insertion, and deletion.
See also:
Data Structure Space and Time Complexity
| Data Structure | Time Complexity | Space Complexity | |||
| Average | Worst | ||||
| Access | Search | Insertion | Deletion | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n log(n)) |
| Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | O(n) |
| Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) |
Sorting Algorithms Space and Time Complexity
| Algorithm | Time Complexity | Space Complexity | ||
| Best | Average | Worst | Worst | |
| Quick Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
| Merge Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Tim Sort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Heap Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | 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(n^2) | O(n) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Cube Sort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
You must log in to post a comment.