Time complexity analysis of most commonly used data structures in computer science
Average Case Asymptotic analysis is denoted using the Theta Notation ( Θ )
Worst case Asymptotic analysis is denoted using Big O Notation ( O )
Best case is denoted using Omega ( Ω )
Data Structure | Average Case Access | Average Case Search | Average Case Insertion | Average Case Deletion | Worst Case Access | Worst Case Search | Worst Case Insertion | Worst Case Deletion |
---|---|---|---|---|---|---|---|---|
Hash Table | Θ(1) | Θ(1) | Θ(1) | O (n) | O (n) | O (n) | ||
Array | Θ(1) | Θ (n) | Θ (n) | Θ (n) | O(1) | O (n) | O (n) | O (n) |
Stack | Θ(n) | Θ (n) | Θ(1) | Θ(1) | O(n) | O (n) | O (1) | O (1) |
Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O (n) | O (1) | O (1) |
B-Tree | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) |
Binary Search Tree | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | O(n) | O(n) | O(n) | O(n) |
AVL Tree | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) |
Red Black Tree | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) |
Splay Tree | Θ( log (n)) | Θ( log (n)) | Θ( log (n)) | O( log (n)) | O( log (n)) | O( log (n)) | ||
Linked- List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O (1) | O (1) |