Sunday 16 October 2016

Common Data Structure Operations with their complexity

Data Structure
Time Complexity
Space Complexity
Average
Worst
Worst
Access
Search
Insertion
Deletion
Access
Search
Insertion
Deletion
Array
Θ(1)
Θ(n)
Θ(n)
Θ(n)
O(1)
O(n)
O(n)
O(n)
O(n)
Stack
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Queue
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Singly-Linked List
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Doubly-Linked List
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Skip List
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(n)
O(n)
O(n)
O(n)
O(n log(n))
Hash Table
N/A
Θ(1)
Θ(1)
Θ(1)
N/A
O(n)
O(n)
O(n)
O(n)
Binary Search Tree
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)
Cartesian Tree
N/A
Θ(log(n))
Θ(log(n))
Θ(log(n))
N/A
O(n)
O(n)
O(n)
O(n)
B-Tree
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Red-Black Tree
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Splay Tree
N/A
Θ(log(n))
Θ(log(n))
Θ(log(n))
N/A
O(log(n))
O(log(n))
O(log(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))
O(n)
KD Tree
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)



Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)