ex3 runtimes

insertion sort

O(N²)

insertion sort (sorted)

O(N)

Simple Sort - lower bound (such as insertion sort, bubble sort, and selection sort)

Ω(N²)

Shell Sort - original sequence

Θ(N²)

Shell Sort- Hibbard’s sequence

Θ(N^3/2)

Shell sort - Sedgewick’s sequence

(O(N^4/3)

Shell Sort - lower bound

Ω(N²)

Shell Sort - upper bound

O(N²)

heap sort, merge sort, quicksort

O(N log N) on average, quicksort worst case O(N²)

quickselect

O(N), worst case O(N²)

bucket sort

O(M+N)

radix sort

O(N)

Union (Array), Find (Array)

union O(N), find O(1) constant. Opposite when tree

Union (Tree), Find (Tree)

union O(1) constant, find O(N). Opposite when array

Smart Union, Smart Find

log(N)

Union, Find - Path compression

O(mlog*N)