332 Runtimes Pt. 2
0.0(0)
Studied by 0 people
Knowt Play
Learn
Practice Test
Spaced Repetition
Match
FlashcardsCard Sorting
1/48
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.
49 Terms
1
New cards
B-Tree insertion/deletion
O(L + Mlog_M(N))
2
New cards
Hash table find with separate chaining
O(n)
3
New cards
Insertion sort average case
O(n²)
4
New cards
Insertion sort best case
O(n)
5
New cards
Selection sort
O(n²)
6
New cards
Heap sort with insert
O(nlogn)
7
New cards
Heap sort with buildHeap
O(n)
8
New cards
AVL sort
O(nlogn)
9
New cards
Sequential Merge sort
O(n)
10
New cards
Sequential Quick sort average
O(nlogn)
11
New cards
Sequential Quick sort worst case
O(n²)
12
New cards
Comparison sorting
Ω(nlogn)
13
New cards
Bucket sort
O(n + k), k = maximum value
14
New cards
Radix sort
O(P*(N+B)), P= digits/passes, B=base/radix
15
New cards
Parallelism on trees
O(logn)
16
New cards
Parallelism on linked lists
O(n)
17
New cards
Parallel Prefix work
O(n)
18
New cards
Parallel Prefix span
O(logn)
19
New cards
Parallel Pack work
O(n)
20
New cards
Parallel Pack span
O(logn)
21
New cards
Parallel Quick Sort
O(log²n)
22
New cards
Parallel Merge Sort
O(log³n)
23
New cards
Number of edges in a dense graph
O(|V|²)
24
New cards
Number of edges in a sparse graph
O(|V|)
25
New cards
Space requirement of an adjacency matrix
O(|V|²)
26
New cards
Adjacency matrix- get a vertex's out-edges
O(|V|)
27
New cards
Adjacency matrix- get a vertex's in-edges
O(|V|)
28
New cards
Adjacency matrix- decide if some edge exists
O(1)
29
New cards
Adjacency matrix- insert edge
O(1)
30
New cards
Adjacency matrix- delete edge
O(1)
31
New cards
Adjacency list space requirements
O(|V|+|E|)
32
New cards
Adjacency list- get a vertex's out-edges
O(d), d = out-degree of vertex
33
New cards
Adjacency list- get a vertex's in-edges
O(|V|+|E|)
34
New cards
Adjacency list- decide if some edge exists
O(d), d = out-degree of vertex
35
New cards
Adjacency list- insert edge
O(1)
36
New cards
Adjacency list- delete edge
O(d), d = out-degree of vertex
37
New cards
Topological sort without queue
O(|V|²+|E|)
38
New cards
Topological sort with queue of zero-degree nodes
O(|V|+|E|)
39
New cards
Depth first search
O(|V|+|E|)
40
New cards
Breadth first search
O(|V|+|E|)
41
New cards
Dijkstra's Algorithm without priority queue
O(|V|²+|E|)
42
New cards
Dijkstra's Algorithm with priority queue holding all unknown nodes, sorted by cost
O(|V|log|V|+|E|log|V|)
43
New cards
Prim's Algorithm with priority queue holding all unknown nodes, sorted by cost
O(|E|log|V|)
44
New cards
Kruskal's Algorithm
O(|E|log|E|) = O(|E|log|V|)
45
New cards
Finding Euler Circuits algorithm
O(|V|+|E|)
46
New cards
Finding Hamiltonian Circuits algorithm
O(b^|V|), b = average branching factor of each node in search tree
47
New cards
Asymptotically optimal parallel execution
O((T₁/P)+T_∞)
48
New cards
How many elements a depth first search stack holds
O(d*p), d = highest out-degree, p = longest path
49
New cards
how many elements a breadth first search queue holds
O(|V|)
Note 
Flashcards (101)