Cheat Sheet

This is a compilation of worst-case complexities for various data-structures and algorithms.

Data-Structures

Data StructureWorst Case Complexity Notes
Array
Insert O(1)
Retrieve O(1)
Linked List
Insert at Tail O(n)
Insert at Head O(1)
Retrieve O(n)

Note that if new elements are added at the head of the linkedlist then insert becomes a O(1) operation.
Binary Tree
Insert O(n)
Retrieve O(n)

In worst case, the binary tree becomes a linked-list.
Dynamic Array
Insert O(1)
Retrieve O(1)

Note by retrieving it is implied we are retrieving from a specific index of the array.
Stack
Push O(1)
Pop O(1)

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
Enqueue O(1)
Dequeue O(1)
Priority Queue (binary heap)
Insert O(lgn)
Delete O(lgn)
Get Max/Min O(1)
Hashtable
Insert O(n)
Retrieve O(n)
Be mindful that a hashtable's average case for insertion and retrieval is O(1)
B-Trees
Insert O(logn)
Retrieve O(logn)
Red-Black Trees
Insert O(logn)
Retrieve O(logn)

Algorithms

CategoryWorst Case Complexity Notes
Sorting
Bubble Sort O(n2)
Insertion Sort O(n2)
Selection Sort O(n2)
Quick Sort O(n2)
Merge Sort O(nlgn)
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
Depth First Search O(n)
Breadth First Search O(n)
Pre-order, In-order, Post-order Traversals O(n)

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 70+ hands-on prep courses.