Given a function and its complexity, what is the complexity of its circuit? For example,
given an element-wise function $f$, with input $x\in\{0,1\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also know the complexity of each individual operations inside $f$. For example, multiplication takes $O(m^{1.585})$ using Karatsuba algorithm, here $m$ is the number of digits of the product. Similarly, suppose that we know all the complexity of arithmetic operations like addition, subtraction, division, square root etc. In addition, suppose that we also know the complexity of all the basic boolean cells, e.g. Full Adder, Subtractor, Multiplier etc.

What is the complexity, in terms of number of boolean gates, of its equivalent boolean circuit? Can we derive a formula containing $n,p,m$?



If so, what is the complexity of a boolean circuits of a Cholesky decomposition, with input $X\in\{0,1\}^{p\times n\times n}$?
There is no mapping from algorithmic complexity to circuit size. A counterexample: consider the language of strings of all ones, $1^n$, for only those $n$ such that the $n$-th Turing Machine rejects the string $1^n$ within $2^{2^n}$ time. Then this function requires $\Omega\left(2^{2^n}\right)$ time to compute on any machine, but the circuit for it only has size $O(n)$, because you can "hard-wire" the answer into the circuit, which then only checks that all the inputs are $1$.

D.W. provides a construction from an algorithm to a circuit. However, note that this gives only an upper bound, which is not necessarily tight. In particular, no function requires circuits of size larger than $O\left(\frac{2^n}{n}\right)$, because that is the size of a circuit which simply enumerates that function's truth table for inputs of size $n$.

Consequently, if an algorithm takes $O(2^{2^n})$ time, then you can use D.W.'s construction for a circuit of size $O(2^{2^n}\log(n)^2)$, but it is immediate that this bound is not tight; there is also a circuit of size $O(\frac{2^n}{n})$, and there may be a much smaller circuit for it, as in the example above. What we really want to know when we ask what is the size of this function's circuit is a lower bound: a minimum size for any circuit.

Circuit size lower bounds is a particularly enigmatic part of computational complexity about which very little is known. For example, we do not know whether or not SAT can be solved with $O(n)$-size circuits, and we have not ruled out that each problem in NEXP can be solved with polynomial-size circuits.