Performance

 Algorithm performance will be measured with repect to size,

that is, the number of gates employed.

                                                           

                                                                                      

Fanout gates are gates that lead to more than 1 next gate. The circuit above has 5

if we ignore the initial fanouts.

 

Circuit depth is not being used here; one considers a layer to be gates that can be run

at the same time because they are independent. Thus the two fanouts above are one layer,

the two NOTs another... Our example has deth 4, gates that can be run in parallel.

Add for each, input length. Below, a half-adder: