$O(n)$ work above the line (up-sweep) since it's $\sum_{i=1}^{\lg(n)-1}{\frac{1}{2^i}}$ sums, which is less than $n$.
$O(n)$ work below the line (down-sweep) since it's $\sum_{i=1}^{\lg(n)-1}{\frac{1}{2^i}}$ sums (in reverse order) in addition to the same amount of copies, which is less than $2n$.
Total work is this $O(n)$, about $3n$. Total span is still $O(\lg n)$, about $2\lg n$.
This comment was marked helpful 0 times.
jpaulson
Another way to understand this slide is to realize that everything but the first and last line is recursively computing scan on the odd-indexed elements.
(actually, that's not quite true. But it's quite close, and you can easily implement it that way)
This comment was marked helpful 0 times.
unihorn
The flow seems to be chaotic at the first glance, but it is not hard to understand it thoroughly.
Imagine an inclusive scan is done in this way. First, it sums all the value in the same way as the first part. Then, it propagates the sum value down in the opposite direction of the first part, and ensures members in each step all have the correct value. ($a_{0-15}$)->($a_{0-7}$, $a_{8-15}$)->($a_{0-3}$, $a_{4-7}$, $a_{8-11}$, $a_{12-15}$)... In the process, it utilizes generated result efficiently.
When it comes to exclusive scan, the easiest way to do this is to move all elements one slot right. But it is unnecessary to waste time to do the extra work because we can break it down and insert into the later part. It maintains a law in each step: for the last $k$th step, the members in the position of $2^k$ multiply have been placed in the relatively correct way. So when it comes to the end, it completes the exclusive scan process.
$O(n)$ work above the line (up-sweep) since it's $\sum_{i=1}^{\lg(n)-1}{\frac{1}{2^i}}$ sums, which is less than $n$.
$O(n)$ work below the line (down-sweep) since it's $\sum_{i=1}^{\lg(n)-1}{\frac{1}{2^i}}$ sums (in reverse order) in addition to the same amount of copies, which is less than $2n$.
Total work is this $O(n)$, about $3n$. Total span is still $O(\lg n)$, about $2\lg n$.
This comment was marked helpful 0 times.
Another way to understand this slide is to realize that everything but the first and last line is recursively computing scan on the odd-indexed elements.
(actually, that's not quite true. But it's quite close, and you can easily implement it that way)
This comment was marked helpful 0 times.
The flow seems to be chaotic at the first glance, but it is not hard to understand it thoroughly.
Imagine an inclusive scan is done in this way. First, it sums all the value in the same way as the first part. Then, it propagates the sum value down in the opposite direction of the first part, and ensures members in each step all have the correct value. ($a_{0-15}$)->($a_{0-7}$, $a_{8-15}$)->($a_{0-3}$, $a_{4-7}$, $a_{8-11}$, $a_{12-15}$)... In the process, it utilizes generated result efficiently.
When it comes to exclusive scan, the easiest way to do this is to move all elements one slot right. But it is unnecessary to waste time to do the extra work because we can break it down and insert into the later part. It maintains a law in each step: for the last $k$th step, the members in the position of $2^k$ multiply have been placed in the relatively correct way. So when it comes to the end, it completes the exclusive scan process.
This comment was marked helpful 0 times.