Big-Oh

CS 3240 Big-Oh
ADT Processing Applications Functions Performance
Average-Case Worst-Case
array unordered key simple/static insert_at_p O(n) O(n)
in contiguous storage find O(n) O(n)
findmin O(n) O(n)
findnext O(n) O(n)
delete_at_p O(n) O(n)
list unordered key complex/dynamic insert_at_p O(1) O(1)
in non-contiguous storage find O(n) O(n)
findmin O(n) O(n)
findnext O(n) O(n)
delete_at_p O(1) O(1)
stack LIFO time-ordered key compilers push O(1) O(1)
automata find O(n) O(n)
balancing findmin O(n) O(n)
infix-to-postfix findnext O(n) O(n)
calculator pop O(1) O(1)
queue FIFO time-ordered key operating systems enqueue O(1) O(1)
breadth-first find O(n) O(n)
findmin O(n) O(n)
findnext O(n) O(n)
dequeue O(1) O(1)
binary search tree partially-ordered lookup insert O(log n) O(n)
hierarchical key dictionary find O(log n) O(n)
findmin O(log n) O(n)
findnext O(log n) O(n)
delete O(log n) O(n)
B+tree ordered databases insert O(log n) O(log n)
hierarchical key find O(log n) O(log n)
findmin O(log n) O(log n)
findnext O(1) O(1)
delete O(log n) O(log n)
priority queue partially-ordered operating systems insert O(log n) O(log n)
(heap) hierarchical key simulation find O(n) O(n)
sorting deletemin O(log n) O(log n)
findnext O(n) O(n)
delete_at_i O(log n) O(log n)
hash table unordered/direct key databases insert O(1) O(n)
compilers find O(1) O(n)
dictionary findmin O(n) O(n)
findnext O(n) O(n)
delete O(1) O(n)
binary search ordered key lookup insert O(n) O(n)
find O(log n) O(log n)
findmin O(1) O(1)
findnext O(1) O(1)
delete O(n) O(n)
sorting ordered key printouts
bubble binary search sort O(n^2) O(n^2)
insertion sort O(n^2) O(n^2)
selection sort O(n^2) O(n^2)
mergesort sort O(nlog n) O(nlog n)
heapsort sort O(nlog n) O(nlog n)
quicksort sort O(nlog n) O(n^2)