INNER CODE UNIT · Python
prefix_or2
lschoe/mpyc · demos/PrefixOrExplained.py:165
def prefix_or2(x):
n = len(x)
y = [None] * n
y[0] = x[0]
for i in range(1, n):
y[i] = y[i-1] | x[i]
return y
# In[11]:
correctness(prefix_or2)
complexity(prefix_or2, 8)
# We need 7 applications of `|` in total. These applications have to be evaluated in a strictly sequential order, which results in the increasing or-depths for the output elements. In general, for an input list `x` of length $n\geq1$, both the or-complexity and or-depth of `prefix_or2(x)` are equal to $n-1$, hence linear in $n$.