Test 1 Flashcards
O(n)
denotes that the function has the same or lower rate of growth than n
Ω(n)
denotes that the function has the same or quicker rate of growth than n
Θ(n)
denotes that the function has the same rate of growth as n
stack-empty complexity
O(1)
stack push complexity
O(1)
stack pop complexity
O(1)
enqueue complexity
O(1)
dequeue complexity
O(1)
list-search
O(n)
list-insert
O(1)
list-delete
O(1)
root
top element of the tree; element with no parents
external node; leaf
a node with no children
internal node
a node with at least one child
tree depth
distance from root to a node
tree height
distance from root to lowest node
preorder, postorder, or inorder traversal complexity
O(n)
preorder traversal
traversal in which a node is visited before its descendants
postorder traversal
traversal in which a node is visited after its descendants
inorder traversal
traversal in which a node is visited after its left subtree and before its right subtree
euler tour traversal
a traversal that walks around the entire tree and has preorder, postorder, and inorder traversal as special cases.
insertion sort average performance
O(n^2)
quick sort average performance
O(n log(n))
merge sort average performance
O(n log(n))
selection sort average performance
O(n^2)
counting sort average performance
O(n+r)
radix sort average performance
O(n * k/d)
heap
a nearly complete binary tree in which each node has a value > its parents value
max-heap-insert
O(log(n))
heap-extract
O(log(n))
max-heapify
O(log(n)
build-max-heap
O(n)
heap sort
O(n log(n))
chaining
a collision-handling strategy in which each entry in the array contains a linked list
linear probing
a collision-handling strategy in which the colliding entry goes to the next linearly available index.
double hashing
a collision-handling strategy in which the colliding entry gets a secondary hash function to find another index.
binary search performance
O(log n)
BST Tree Insert
O(h)
BST Tree Delete
O(h)
RBT Tree Insert
O(log n)
RBT Tree Delete
O(log n)
