In up-sweep function, workload is N, span is lg N.
In Down-sweep function, workload is 2N, span is lg N.
So the constant here is 3 and 2.
In fact, we really care about the constant. And the constant before N in workload can be improved to 1.5 in slides 23
In up-sweep function, workload is N, span is lg N. In Down-sweep function, workload is 2N, span is lg N. So the constant here is 3 and 2. In fact, we really care about the constant. And the constant before N in workload can be improved to 1.5 in slides 23
This comment was marked helpful 0 times.