I think the constant of Work is 2.
For up-sweep, it is $1+2+...+n/2 \approx n$.
For down-sweep, it is $n/2+...+2+1 \approx n$.
P.S. here we just consider arithmetic operation use O(1) time. I do not take load save time into account.
The constant of span is 2.
The max span for up-sweep is 1 time of logn.
The max span for down-sweep is 1 time of logn.
qqkk
what does the span mean ?
karima
@qqkk Span is the longest sequence of operations that must be performed sequentially in an algorithm. The span of an algorithm is determined by the inherent data dependencies in the algorithm.
For example: say I have 3 tasks, A, B, and C. Task B needs the output of task A. Task C doesn't need anything from A or B. So the span is 2. If each task takes unit time, the max speedup I can possibly have is 3/2.
I think the constant of Work is 2. For up-sweep, it is $1+2+...+n/2 \approx n$. For down-sweep, it is $n/2+...+2+1 \approx n$.
P.S. here we just consider arithmetic operation use O(1) time. I do not take load save time into account.
The constant of span is 2. The max span for up-sweep is 1 time of logn. The max span for down-sweep is 1 time of logn.
what does the span mean ?
@qqkk Span is the longest sequence of operations that must be performed sequentially in an algorithm. The span of an algorithm is determined by the inherent data dependencies in the algorithm.
For example: say I have 3 tasks, A, B, and C. Task B needs the output of task A. Task C doesn't need anything from A or B. So the span is 2. If each task takes unit time, the max speedup I can possibly have is 3/2.