Final Flashcards
Unsorted Array search
O(N)
Unsorted Array insert
O(1)
Unsorted Array del
O(1)
Unsorted Array mem
Wasteful
Sorted Array search
O(logN)
Sorted Array insert
O(N)
Sorted Array del
O(N)
Sorted Array mem
Wasteful
Sorted LL search
O(N)
Sorted LL insert
O(N)
Sorted LL del
O(1)
Sorted LL mem
Efficient
Bal BST search
O(logN)
Bal BST insert
O(logN)
Bal BST del
O(logN)
Bal BST mem
Efficient
LL Push
O(1)
LL Pop
O(1)
AL Push
O(N)/O(1)
AL Pop
O(N)/O(1)
AL Enq
O(N)/O(1)
AL Deq
O(N)/O(N)
LL Enq
O(1)
LL Deq
O(1)
AL circular Enq
O(N)/O(1)
AL circular Deq
O(N)/O(1)
Heap insert
O(N)/O(logN)
Heap search
O(N)/O(N)
Heap delete
O(N)/O(logN)
Heap enq
O(N)/O(logN)
Heap deq
O(N)/O(logN)
Heap build
O(N)
Bal Bst insert
O(logN)
Bal BST search
O(logN)
Bal BST del
O(logN)
Bal BST enq
O(logN)
Bal BST deq
O(logN)
Bal BST build
O(NlogN)
Hash insert
O(N)/O(1)
Hash search
O(1)
Hash del
O(N)/O(1)
Hash enq
O(N)/O(1)
Hash deq
O(N)
Hash build
O(N)
Selection sort worst
O(N^2)
Selection sort best
O(N^2)
Selection sort average
O(N^2)
Selection sort space
O(1)
Bubble sort worst
O(N^2)
Bubble sort best
O(N)
Bubble sort average
O(N^2)
Bubble sort space
O(1)
Quicksort worst
O(N^2)
Quicksort best
O(NlogN)
Quicksort average
O(NlogN)
Quicksort space
O(logN)
Heapsort worst
O(NlogN)
Heapsort best
O(NlogN)
Heapsort average
O(NlogN)
Heapsort space
O(1)
Dijkstra’s complexity
O(M log N) (edges)
