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) |