On this page, you can quickly calculate asymptotic complexity growing based on operations balance with the data structure.
Please note, this is a just basic rough calculation based on asymptotic time complexity. This calculator ignores many factors
which affect performance in the real application.
Also, in some cases (for example for the Dynamic array) amortized cost is used.
Calculator
Estimated structure size: elements
Lower index in the result table is better. Index = 1.00 – it’s reference, other indexes shows complexity growing relative to the reference.
Source data
Data structure complexities used for calculations
| Data Structure | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | ||||
|---|---|---|---|---|---|---|---|
| Search | Insertion | Deletion | Search | Insertion | Deletion | ||
| Dynamic array | O(n) | O(1) | O(1)* | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Skip List | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n * log(n)) |
| Hash Table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) |
| B-Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Red-Black Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| KD Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) |
* Amortized cost