Big O Asymptotic Time Complexity – Common Data Structures

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)

Leave a Comment