INNER CODE UNIT · Python

h

lschoe/mpyc · demos/PrefixOrExplained.py:247

        h = (i + j)//2
        if i < h:
            pf(i, h)
            a = x[h-1]
            pf(h, j)
            x[h:j] = (a | b for b in x[h:j])  # all |s in parallel in 1 round
            
    n = len(x)
    x = x[:]
    pf(0, n)
    return x


# We analyze the complexity of `prefix_or4()` for input lists of length $n=2^k$, $k\geq0$, as follows.
# Let $T_n$ and $R_n$ denote the or-complexity and or-depth of `prefix_or4()`, respectively. For the or-complexity we have as recurrence relation $T_1 = 0$, $T_n = 2 T_{n/2} + n/2$ with solution $T_n = (n/2) \log_2 n$. And for the or-depth we have $R_1=0$ and $R_n=R_{n/2} +1$ with solution $R_n=\log_2 n$, as we need only one round at each level of the recursion.
# 
# For $n=8$ we thus get $(8/2) \log_2 8 = 12$ as or-complexity and $\log_2 8 =3$ as or-depth:

View source record →