# What is the counting argument for the number of elementary operations required for a random function?

What is the counting argument for the following statement (classical)?

"A random function on n bits requires $$e^{\Omega(n)}$$ elementary operations."

It appears in the introduction of PRL 116, 170502 (2016): Efficient Quantum Pseudorandomness.

Is it that since there are infinitely many n-bit boolean functions, implementing one such randomly chosen function using elementary operations would require an exponentially large number? (I'm assuming that elementary operations here mean two-bit universal gates.)

Also, why $$\Omega(n)$$ and not $$O(n)$$?

• $\Omega(n)$ generally means lower bound, while $O(n)$ means upper bound, does that answer your question? Also, there are $2^n$ boolean functions, not an infinite number. Jun 11, 2021 at 13:52
• Yes, that makes sense. I somehow missed the Boolean part. So, $2^n=e^{ln 2^n} \approx e^{\Omega(n)}$. Thanks! Jun 11, 2021 at 15:17
We say that a function $$f(n)$$ is $$O(n)$$ if its bounded above by $$n$$ asymptotically, which is not to be confused with a function $$f(n)$$ being $$\Omega(n)$$ which means that $$f(n)$$ is bounded below by $$n$$ asymptotically.
Also, there are $$2^n$$ boolean functions on $$\{0,1\}^n$$ since each boolean function $$f:\{0,1\}^n\rightarrow \{0,1\}$$ is in one-to-one correspondence with a subset $$S$$ of $$\{1,2,\ldots,n\}$$ via the identification $$f^{-1}(1)=S$$.
So like you said in the comments $$2^n=e^{\Omega(n)}$$.