INNER CODE UNIT · Python
y
lschoe/mpyc · demos/PrefixOrExplained.py:167
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$.
# Linear or-complexity is unavoidable, but linear or-depth (round complexity) is bad news. We want to have *sub-linear* round complexity, for instance, proportional to $\sqrt n$, or rather **logarithmic** round complexity proportional to $\log n$: otherwise, the wait time for exchanging secret-shares between the parties will probably dominate the overall performance.