Porovnanie dvoch neklesajúcich postupností 3, PA
Paralelná architektúra (PA):
f[u] ? { g[i] | 0 ? i ? N } ?
? ? v: 0 ? v < N :: ?(g[v] < f[v] < g[v + 1])?
musíme teda pocítat predikát
? ? u, v : 0 ? u < N, 0 ? v < N :: ?(g[v] < f[u] < g[v + 1])? ?
? ? u, v : 0 ? u < N, 0 ? v < N :: ?(g[u] < f[v] < g[u + 1])?
zjednodušením tohoto predikátu dostaneme
? ? u, v : 0 ? u, v < N ::
O(N2) konjunkcií a kazdá je disjunkciou 3 castí:
cas O(log N) na O(N2) synchrónnych procesoroch