Cost and delay of a combinational circuits

[barak]

Hello,
In ch.7 part 2 we learned when given a reccurence equation how to find the sum of penalties and the rate of growth using a recursive tree.
How does the sum of penalties and the rate of growth are related to the cost and delay of a combinational circuits?
Is there even a connection or Im confusing two different subjects?

For example Guy found in ch.15 (time ~ 33:00) the c(CSA(n)) and d(CSA(n)) using only reccurence equation, without any recursive tree.
I would appreciate if you could specify the steps for finding the cost and delay of combinational circuits.

Thanks and happy Shavuot.

[guyeven]

Functions are used for counting the cost/delay of a circuit parametrized by n (say, the length of the input).
When the circuits are defined recursively, it is convenient to define these functions using recurrences.
One technique for solving recurrence equations is to build the recursion tree and sum the penalties across the tree.
Once we solve a recurrence equation, we may use this solution whenever we encounter the equation again.

[barak]

@guyeven

counting the cost/delay of a circuit parametrized by nn (say, the length of the input).
When the circuits are defined recursively, it is convenient to define these functions using recurrences.
One technique for solving recurrence equations is to build the recursion tree and sum the penalties across the tree.
Once we solve a recurrence equation, we may use this solution w

But the sum of penalties(or in other words the rate of growth) indicates the cost or the delay?

[Alon_Lukatch]

Hello Barak,

The sum of the penalties can indicate either the cost or the delay, depends on what penalties you’re counting. I recommend re-watching the lecture / recitation about the definitions of cost and delay of a circuit.