Parallel Prefix Sum, Work Computation

Question

In the skript PRAM Basics on page 68 there is the work of the algorithm parallel prefix sum given as a comment. For the bottom-up traversal the work is n-1 and for the top-down traversal the work is n-log(n)-1. How are these values computed?

W_{bottom-up}(N) = sum h=1, log(N) W_h(N) = sum h=1, log(N) N/(2^h) =...= n-1

W_{top-down}(N) = sum h=1, log(N)-1 W_h(N) = sum h=1, log(N)-1 N/(2^h)-1 = ... = n-log(n)-1

Answer 1

For the computation of the work, we need the geometric sum formula which is \sum_{i=1}^n q^i = q*\frac{q^n-1}{q-1}.

The work of the bottom-up traversal is then computed as follows:

    W_{bottom-up}(n) 
        = \sum_{h=1}^{\log(n)} \frac{n}{2^h}
        = n * \sum_{h=1}^{\log(n)} \frac{1}{2}^h
        = n * \frac{1}{2} * \frac{\frac{1}{2}^\log{n}-1}{\frac{1}{2}-1}
        = n * \frac{1}{2} * \frac{\frac{1}{n}-1}{\frac{1}{2}-1}
        = \frac{1}{2} * \frac{1-n}{\frac{1}{2}-1}
        = \frac{1-n}{1-2}
        = \frac{1-n}{-1}
        = n-1

The work of the top-down traversal is computed as follows:

    W_{top-down}(n) 
        = \sum_{h=1}^{\log(n)-1} (\frac{n}{2^{\log(n)-i}} - 1) 
        = (\sum_{h=1}^{\log(n)-1} \frac{n}{2^{\log(n)-i}}) - (\log(n)-1)
        = (\sum_{h=1}^{\log(n)-1} \frac{n*2^i}{2^{\log(n)}}) - (\log(n)-1)
        = (\sum_{h=1}^{\log(n)-1} \frac{n*2^i}{n}) - (\log(n)-1)
        = (\sum_{h=1}^{\log(n)-1} 2^i) - (\log(n)-1)
        = (2*\frac{2^{\log(n)-1}-1}{2-1}) - (\log(n)-1)
        = (2* {2^{\log(n)-1}-1}) - (\log(n)-1)
        = (2* {n/2-1}) - (\log(n)-1)
        = (n - 2) - (\log(n)-1)
        = n - 2 - \log(n) + 1
        = n - \log(n) - 1