CSE 332 Final Exam Runtimes Flashcards

Selection sort (worst case)

n^2

Selection sort (best case)

n^2

insertion sort (worst case)

n^2

insertion sort (best case)

n

heap sort (both in-place and not --> best case)

nlogn

heap sort (both in-place and not --> worst case)

nlogn

Merge sort (best case)

nlogn

Merge sort (worst case)

nlogn

Quicksort (best case)

nlogn

Quicksort (worst case)

n^2

bucket sort (average/best)

n + k

bucket sort (worst case)

n^2

radix sort (average)

nlog_b(m) + blog_b(m)

dense graph equation

|E| in Big-Theta(|V|^2)

sparse graph equation

|E| in Big-theta(|V|)

max number of edges in a graph

Big-theta(|V|^2)

max number of edges in undirected and simple graph

(|V|(|V| - 1)) / 2

max number of edges in directed and simple graph

|V|(|V| - 1)

max number of edges in direct and non-simple (but no duplicates) graph

|V|^2

if graph is connected, the min number of edges

|V| - 1

BFS runtime

Big-theta(|V| + |E|)

DFS runtime

Big-theta(|V|+|E|)

Dijkstra's algorithm runtime

big-theta(|E|log|V|)

prim's runtime

ElogV

Euler's runtime

V + E