3 ms·

I'm confused. Since O(log n) is faster than O(n) why would O(n) require a little more work? Did I misread something or did you miswrite?

• pfdietz 3y ago
  I'm talking about constructing boolean circuits. The usual parallel prefix algorithm yields a circuit of depth O(log n) with O(n log n) gates. Using some trickery, however, this can be reduced to O(n) gates, with a constant factor increase in depth. https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Adder_(electronics) https://en.wikipedia.org/wiki/Adder_(electronics)
  • ithkuil 3y ago
    Constant depth requires unbounded fan-in, which may not be available in practice
    • pfdietz 3y ago
      Yes, I was talking about using gates of bounded fan-in.