Big O Flashcards
Insert in ordered array
O(n)
Removal from ordered array
O(n)
Linear Search # of comparisons Best Case
found as first element
1 comparison
Linear Search # of comparisons worst case
n comparisons
when element is last element or not in the array
Linear Search number of comparisons in average case
(3n+1)/4 comparisons
Binary Search # of comparisons best case
1 comparison
element wanted is in the middle of the array
Binary search # of comparisons worst case
log(n) + 1 comparisons
Binary Search # of comparisons average case
closer to worst case then best case
more likely to find the element as the search space gets smaller
Selection Sort Barometer Operation
n*(n-1)/2
Selection Sort # of swaps
n-1
Insertion sort # of comparisons Worst case
n*(n-1)/2
Insertion sort # of comparisons best case
n comparisons (no moves)
Insertion sort # of comparisons average case
n*(n-1)/4
Quick sort best case run time
O(n log n)
Quick sort average case run time
O( n log n)
Quick sort worst case run time
O(n^2)
Selection sort best case run time
O(n^2)
Selection sort average case run time
O(n^2)
Selection sort worst case run time
O(n^2)
Insertion sort best case run time
O(n)
Insertion sort average case run time
O(n^2)
Insertion sort worst case run time
O(n^2)
Mergesort best case run time
O(n log n)
Merge sort average case run time
O(nlogn)
Merge sort worst case run time
O(nlogn)
HeapSort best case run time
O(nlogn)
HeapSort average case run time
O(nlogn)
HeapSort worst case run time
O(nlogn)
Data structure- insertion, delete, look up - run time
O(log n)
BST insertion, removal, search cost
O(height)
sorting an array with BST run time
O(n * h)
if balanced than O(nlogn)
Run time of Priority Queues insert and remove
O(log n)
Heap # of swaps for insertion
height swaps
Heap number of comparisons for removal
height * 2 compariosns
Run time for insertions and removal from a heap
O(log n)
Heap removal of a node run time
O(logn)
Heap removal of a node run time
O(nlogn)
cost to heapify an array
O(n)
Time complexity of Radix Sort
O(n*k)
where n values of at most k digits
