Array (Static)
Search: O(N)
Insert: O(1)
Delete: O(1)
Sorted Array
Search: O(log N)
Insert: O(N)
Delete: O(N)
Sorted Linked List
Search: O(N)
Insert: O(N)
Delete: O(1)
Balanced Binary Search Tree (BST)
Search: O(log N)
Insert: O(log N)
Delete: O(log N)
Stack (using Linked List or ArrayList)
Push: O(1)
Amortized for ArrayList
Pop: O(1)
Amortized for ArrayList
Queue (Linked List)
Enqueue: O(1)
Dequeue: O(1)
Queue (ArrayList Non-Circular)
Enqueue: O(N) worst case / O(1) amortized
Dequeue: O(N)
Queue (ArrayList Circular)
Enqueue: O(1) amortized
Dequeue: O(1) amortized
Priority Queue (using Heap)
Enqueue: O(log N) amortized
Dequeue (remove max): O(log N) amortized
Build Heap from Array (Build-Heap): O(N)
AVL Tree
Insert: O(log N)
Delete: O(log N)
Search: O(log N)
Red-Black Tree
Insert: O(log N)
Delete: O(log N)
Search: O(log N)
Hash Table
With good hash function, Search: O(1) average
Hash Table (Chaining): Insert: O(1) average
Hash Table (Probing): Insert: O(1) average
Worst Case Search: O(N)
Selection Sort
Time Complexity (Best/Worst/Average): O(N^2)
Bubble Sort
Best Case: O(N)
Worst/Average: O(N^2)
Quicksort
Best/Average: O(N log N)
Worst: O(N^2)
Heapsort
All Cases: O(N log N)
Selection Sort, Bubble Sort, Heapsort: O(1)
Quicksort: O(log N) (recursive stack) or O(N) (worst case without optimizations)
Dijkstra's Algorithm
Time Complexity: O((n + m) log n)
BFS Shortest Path
Time Complexity: O(n + m)