CSE 332 Final Exam Runtimes Flashcards

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/24

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

25 Terms

1
New cards
Selection sort (worst case)
n^2
2
New cards
Selection sort (best case)
n^2
3
New cards
insertion sort (worst case)
n^2
4
New cards
insertion sort (best case)
n
5
New cards
heap sort (both in-place and not --> best case)
nlogn
6
New cards
heap sort (both in-place and not --> worst case)
nlogn
7
New cards
Merge sort (best case)
nlogn
8
New cards
Merge sort (worst case)
nlogn
9
New cards
Quicksort (best case)
nlogn
10
New cards
Quicksort (worst case)
n^2
11
New cards
bucket sort (average/best)
n + k
12
New cards
bucket sort (worst case)
n^2
13
New cards
radix sort (average)
nlog_b(m) + blog_b(m)
14
New cards
dense graph equation
|E| in Big-Theta(|V|^2)
15
New cards
sparse graph equation
|E| in Big-theta(|V|)
16
New cards
max number of edges in a graph
Big-theta(|V|^2)
17
New cards
max number of edges in undirected and simple graph
(|V|(|V| - 1)) / 2
18
New cards
max number of edges in directed and simple graph
|V|(|V| - 1)
19
New cards
max number of edges in direct and non-simple (but no duplicates) graph
|V|^2
20
New cards
if graph is connected, the min number of edges
|V| - 1
21
New cards
BFS runtime
Big-theta(|V| + |E|)
22
New cards
DFS runtime
Big-theta(|V|+|E|)
23
New cards
Dijkstra's algorithm runtime
big-theta(|E|log|V|)
24
New cards
prim's runtime
ElogV
25
New cards
Euler's runtime
V + E