Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).
My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)
Time complexity is often defined as the "number of operations in the worst case for a Turing machine." The monotone circuit model of computation is not the Turing time model. Thus it is not meaningful to say what the time complexity of such a circuit is.
On the other hand, if we view the monotone circuit model as a model of actual circuits, then one "time cost" of computation is the depth of such a circuit. Thus in that sense the time complexity of the circuit you mention is 5.3log(n).
Of course, in real circuits there are other factors besides "depth" that contribute to "how long it takes to do the computation." For example, the longest wire in a circuit often is bottleneck in actual VLSI computation as its larger capacitance takes longer to charge.
