CSE 332

o(nlogn)

quicksort best case

o(nlogn)

quicksort average case

o(n²)

quicksort worst case

no

is quicksort stable

yes

is quicksort in place

o(n²)

selection sort best-case, average case, worst case

o(nlogn)

merge sort best case, average case, worst case

o(n²)

insertion sort average case and worst case

o(n)

insertion sort best case

no

is selection sort stable

yes

is selection in place

yes

is merge sort stable

no

is merge sort in place

yes

is insertion sort stable

yes

is insertion sort in place

o(nlogn)

heap sort best, average, and worst case

no

is heap sort stable

yes

is heap sort in place

O(nk)

radix sort best, average, and worst case

yes

is radix sort stable

no

is radix sort in-place

o(n+k)

bucket sort best case and average case

o(n²)

bucket sort worst case

yes

is bucket sort stable

no

is bucket sort in place

o(1 + x)

let x be the load factor, what is the time complexity of separate chaining

o(1 + 1/(1-x))

let x be the load factor, what is the time complexity of linear probing, quadratic probing, and double hashing?

T1/Tp <= 1/(S + (1 - S) / P)

Amdahl’s law with P processors and sequential runtime of S

2^h

minimum number of nodes in binary minheap

2^(h+1) - 1

maximum number of nodes in binary minheap