Intro to CS- Brilliant.org

Page 1

Binary Search:

1000 elements

Need at most comparisons:

[log(base 2) 1000]+1 comparisons

Insertion sort:

Place the element you want to add at the end of the list/array and compare it with the left element. If it is smaller than the left element, swap them and repeat. Otherwise, we are done.

Worst case for insertion sort:

(n)(n-1)/2 comparisons

Best case for insertion sor:

n-1 comparisons