INNER CODE UNIT · Python
prefix_or4
lschoe/mpyc · demos/PrefixOrExplained.py:245
def prefix_or4(x):
def pf(i, j):
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.
#