Big O Flashcards
(39 cards)
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)
