Complexities Flashcards
1
Q
Serial Map?
A
Work = O(n) Span = O(n)
2
Q
Parallel Map?
A
Work = O(n) Span = O(1)
3
Q
Serial Reduction?
A
Work = O(n) Span = O(n)
4
Q
Parallel Reduction?
A
Work = O(n) Span = O(log n)
5
Q
Serial Scan?
A
Work = O(n) Span = O(n)
6
Q
Span Efficient Hillis-Steele Scan?
A
Work = O(nlogn) Span = O(log n)
7
Q
Work Efficient Blelloch Scan?
A
Work = O(n) Span = O(log n)
8
Q
Parallel Gather/Scatter?
A
Same as map
Work = O(n)
Span = O(1)
9
Q
Serial Bubblesort?
A
Work = O(n2)
10
Q
Linear Search?
A
Work = O(n) Span = O(n)
11
Q
Odd-Even Sort?
A
Work = O(n2) Span = O(n)
12
Q
Bitonic Sort?
A
Work = O(nlog2n) Span = O(log2n)
13
Q
Binary Search?
A
O(logn)
14
Q
P-ary Search?
A
Span = O(logpn)
