Arrays
- Set, Check element at a particular index: O(1)
- Searching: O(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used,
- Similarly,
Insert
for arrays is basicallySet
as mentioned in the beginning
ArrayList:
- Add: Amortized O(1)
- Remove: O(n)
- Contains: O(n)
- Size: O(1)
Linked List:
- Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Searching: O(n)
Doubly-Linked List:
- Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Deleting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
- Searching: O(n)
Stack:
- Push: O(1)
- Pop: O(1)
- Top: O(1)
- Search (Something like lookup, as a special operation): O(n) (I guess so)
Queue/Deque/Circular Queue:
- Insert: O(1)
- Remove: O(1)
- Size: O(1)
Binary Search Tree:
- Insert, delete and search: Average case: O(log n), Worst Case: O(n)
Red-Black Tree:
- Insert, delete and search: Average case: O(log n), Worst Case: O(log n)
Heap/PriorityQueue (min/max):
- Find Min/Find Max: O(1)
- Insert: O(log n)
- Delete Min/Delete Max: O(log n)
- Extract Min/Extract Max: O(log n)
- Lookup, Delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST
HashMap/Hashtable/HashSet:
- Insert/Delete: O(1) amortized
- Re-size/hash: O(n)
- Contains: O(1)
Searching & Sorting Algorithm |
Best case |
Worst case |
---|---|---|
Selection sort | O(N^{2}) | O(N^{2}) |
Merge sort | O(N log N) | O(N log N) |
Linear search | O(1) | O(N) |
Binary search | O(1) | O(log N) |
Heapsort | O(n log(n)) | O(n log(n)) |
Bubble Sort | O(n) | O(n^2) |
Insertion Sort | O(n) | O(n^2) |