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