Time complexities of different data structures
Time Complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to process or run as a function of the amount of input. In other words, the time complexity is how long a program takes to process a given input. The efficiency of an algorithm depends on two parameters:
- Time Complexity
- Space Complexity
Time Complexity: It is defined as the number of times a particular instruction set is executed rather than the total time taken. It is because the total time taken also depends on some external factors like the compiler used, the processor’s speed, etc.
Space Complexity: It is the total memory space required by the program for its execution.
Best case time complexity of different data structures for different operations
Data structure | Access | Search | Insertion | Deletion |
---|---|---|---|---|
Array | O(1) | O(1) | O(1) | O(1) |
Stack | O(1) | O(1) | O(1) | O(1) |
Queue | O(1) | O(1) | O(1) | O(1) |
Singly Linked list | O(1) | O(1) | O(1) | O(1) |
Doubly Linked List | O(1) | O(1) | O(1) | O(1) |
Hash Table | O(1) | O(1) | O(1) | O(1) |
Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) |
AVL Tree | 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) |
Red Black Tree | O(log n) | O(log n) | O(log n) | O(log n) |
Worst Case time complexity of different data structures for different operations
Data structure | Access | Search | Insertion | Deletion |
---|---|---|---|---|
Array | O(1) | O(N) | O(N) | O(N) |
Stack | O(N) | O(N) | O(1) | O(1) |
Queue | O(N) | O(N) | O(1) | O(1) |
Singly Linked list | O(N) | O(N) | O(N) | O(N) |
Doubly Linked List | O(N) | O(N) | O(1) | O(1) |
Hash Table | O(N) | O(N) | O(N) | O(N) |
Binary Search Tree | O(N) | O(N) | O(N) | O(N) |
AVL Tree | O(log N) | O(log N) | O(log N) | O(log N) |
Binary Tree | O(N) | O(N) | O(N) | O(N) |
Red Black Tree | O(log N) | O(log N) | O(log N) | O(log N) |
The average time complexity of different data structures for different operations
Data structure | Access | Search | Insertion | Deletion |
---|---|---|---|---|
Array | O(1) | O(N) | O(N) | O(N) |
Stack | O(N) | O(N) | O(1) | O(1) |
Queue | O(N) | O(N) | O(1) | O(1) |
Singly Linked list | O(N) | O(N) | O(1) | O(1) |
Doubly Linked List | O(N) | O(N) | O(1) | O(1) |
Hash Table | O(1) | O(1) | O(1) | O(1) |
Binary Search Tree | O(log N) | O(log N) | O(log N) | O(log N) |
AVL Tree | 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) |
Red Black Tree | O(log N) | O(log N) | O(log N) | O(log N) |
Related Article on Time and Space Complexity:
- Time and Space Complexity of Binary Search
- Time and Space Complexity of Linear Search
- Time and Space Complexity of Ternary Search
- Time and Space Complexity of Breadth First Search (BFS)
- Time and Space Complexity of Depth First Search (DFS)
- Time and Space Complexity of Insertion Sort
- Time and Space Complexity of Selection Sort
- Time and Space Complexity of Bubble Sort
- Time and Space Complexity of Quick Sort
- Time and Space Complexity of Merge Sort
- Time and Space complexity of Radix Sort Algorithm
- Time and Space Complexity of Linked List
- Time and Space Complexity of Floyd Warshall Algorithm
- Time and Space Complexity of Bellman–Ford Algorithm
- Time and Space Complexity of Dijkstra’s Algorithm
- Time and Space Complexity Analysis of Prim’s Algorithm