Complexity Analysis Flashcards
Implementation of Binary Search Tree
Children Pointers
BST insert
0(n)
BST delete
O(n)
BST Search
O(n)
BST deleteMin
O(n)
BST deleteMax
O(n)
Building BST using insert
O(n^2)
Building optimal BST using dynamic programming algorithm
O(n^3)
Implementation of 2-3 Tree
Children/parent pointers
2-3 Tree insert
O(lgn)
2-3 Tree delete
O(lgn)
2-3 Tree search
O(lgn)
2-3 Tree findMin
O(lgn)
2-3 Tree findMax
O(lgn)
2-3 Tree buildTree
O(nlgn)
implementation of k-heap
array-based
k-heap insert
O(lgn)
k-heap general delete
O(n)
k-heap general search
O(n)
min k-heap deleteMax
O(n)
min k-heap deleteMin
O(lgn)
max k-heap deleteMax
O(lgn)
max k-heap deleteMin
O(n)
k-heap top-down build
O(nlgn)
k-heap bottom-up build
O(n)
k-heap frequent insertions
want larger k
k-heap frequent deletions
want smaller k
dual-heap insert
O(lgn)
dual-heap deleteMin
O(lgn)
dual-heap deleteMax
O(lgn)
dual-heap findMin
O(1)
dual-heap findMax
O(1)
dual-heap buildHeap
O(n)
implementation of minmax/maxmin heap
sequential array-based with root at A[1]
minmax/maxmin heap insert
O(lgn)
minmax/maxmin deleteMin
O(lgn)
minmax/maxmin deleteMax
O(lgn)
minmax/maxmin top-down build
O(nlgn)
minmax/maxmin bottom-up build
O(n)
minmax/maxmin findMin
O(1)
minmax/maxmin findMax
O(1)
implementation of leftist heap
children pointers
leftist heap concate
O(lgn)
leftist heap insert
O(lgn)
leftist heap deleteMin (for min leftist)
O(lgn)
leftist heap deleteMax (for max leftist)
O(lgn)
leftist heap findMin (for min leftist)
O(1)
leftist heap findMax( for max leftist)
O(1)
leftist heap buildHeap using insert
O(nlgn)
implementation of skew heap
children pointers
skew heap concate
O(n)
skew heap insert
O(n)
skew heap deleteMin (for min skew heap)
O(n)
skew heap deleteMax (for max skew heap)
O(n)
skew heap findMin (for min skew heap)
O(1)
skew heap findMax( for max skew heap)
O(1)
skew heap buildHeap using insert
O(n^2)
implementation of pairing heap
left-child right-sibling pointers
pairing heap merge
O(1)
pairing heap insert
O(1)
pairing heap findMin (for min pairing heap)
O(1)
pairing heap findMax (for max pairing heap)
O(1)
pairing heap deleteMin (for min pairing heap)
O(n)
pairing heap deleteMax (for max pairing heap)
O(n)
pairing heap buildHeap using insert
O(n)
What structure(s) are search trees?
binary search trees
2-3 trees
What structure(s) are priority queues?
k-heaps
What structure(s) are double-ended priority queues?
dual-heaps
minmax/maxmin heaps
What structure(s) are concatenated queues?
leftist heaps
skew heaps
pairing heaps
Binomial Queue concate
O(lgn)
Binomial Queue insert
O(lgn)
Binomial Queue deleteMin
O(lgn)
Binomial Queue findMin
O(lgn)
Binomial Queue Build
O(nlgn)
Fibonacci Heap concate
O(1)
Fibonacci Heap insert
O(1)
Fibonacci Heap deleteMin
O(n)
Fibonacci Heap findMin
O(1)
Fibonacci Heap decreaseKey
O(lgn)
Fibonacci Heap delete
O(n)
AVL tree find
0(lgn)
AVL tree findMin
O(lgn)
AVL tree findMax
O(lgn)
AVL tree delete
O(lgn)
AVL tree deleteMin
O(lgn)
AVL tree deleteMax
O(lgn)
AVL tree insert
O(lgn)
