# Algorithm Complexity

## Arrays

• Set, Check element at a particular index: O(1)
• SearchingO(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 basically `Set` as mentioned in the beginning

## ArrayList:

• RemoveO(n)
• ContainsO(n)
• SizeO(1)

• InsertingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• DeletingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
• SearchingO(n)

• InsertingO(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.
• DeletingO(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.
• SearchingO(n)

## Stack:

• PushO(1)
• PopO(1)
• TopO(1)
• Search (Something like lookup, as a special operation): O(n) (I guess so)

• InsertO(1)
• RemoveO(1)
• SizeO(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 MaxO(1)
• InsertO(log n)
• Delete Min/Delete MaxO(log n)
• Extract Min/Extract MaxO(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/DeleteO(1) amortized
• Re-size/hashO(n)
• ContainsO(1)

### Worst case

Selection sort O(N2) O(N2)
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) 