On the complexity of the monotonicity verification
A.A. Voronenko · 2002
We present a sequence {S/sub n/} of circuits of functional elements that check the monotonicity of input discrete functions depending on n variables and represented as value column vectors. The complexity of circuits equals O(N/spl radic/log log N). This is the lowest asymptotical current complexity.