To represent complexity of an algorithm, Computer Scientist is used to using big-O notation.
How about complexity of boolean algebra?
Boolean algebra is commonly used in digital circuit design with using logic gates, practically useful in FPGA programming. Speaking about logic gates circuit, This topic maybe looks like Computer Engineering question, but I think it's okay to ask in Computer Science. Actually Computer Scientist and Computer Engineer doesn't need to know about Electrical Engineering at all to know about it, because logic gates already an abstraction of electrical stuff, all we just need to know is Input->Logic->Output
where Input/Output are just bunch of 0
and 1
.
What I mean about complexity of boolean algebra is actually complexity of logic gates circuit. As we know, if an input propagate to a logic gate for example a NOT
gate, it needs time to propagate, if there's NOT
gate again (more step), then more time to consume, hence that's circuit is going to complex.
Look this case for example,
- #1
Z = NOT(X)
is equivalent with - #2
Z = NOT(NOT(NOT(X)))
- Where Z is output and X is an input.
But they are different in complexity. Practically (eg: FPGA programming), #2 is slower than #1 due to three steps to propagate while #1 is just one step to pass.