Cheat Sheet
This is a compilation of worst-case complexities for various data-structures and algorithms.
Data-Structures
Data Structure | Worst Case Complexity | Notes | ||||||
---|---|---|---|---|---|---|---|---|
Array |
|
|||||||
Linked List |
|
Note that if new elements are added at the head of the linkedlist then insert becomes a O(1) operation. |
||||||
Binary Tree |
|
In worst case, the binary tree becomes a linked-list. |
||||||
Dynamic Array |
|
Note by retrieving it is implied we are retrieving from a specific index of the array. |
||||||
Stack |
|
There are no complexity trick questions asked for stacks or queues. We only mention them here for completeness. The two data-structures are more important from a last-in last-out (stack) and first in first out (queue) perspective. |
||||||
Queue |
|
|||||||
Priority Queue (binary heap) |
|
|||||||
Hashtable |
|
Be mindful that a hashtable's average case for insertion and retrieval is O(1) | ||||||
B-Trees |
|
|||||||
Red-Black Trees |
|
Algorithms
Category | Worst Case Complexity | Notes | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Sorting |
|
Note, even though worst case quicksort performance is O(n2) but in practice quicksort is often used for sorting since its average case is O(nlgn). | ||||||||||
Trees |
|
n is the total number of nodes in the tree. Most tree-traversal algorithms will end up seeing every node in the tree and their complexity in the worst case is thus O(n). |
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.