Lesson 1

Now that we have a complexity measure for functions, it is natural to ask: what is the maximum circuit complexity of a function from \(B_{n}\)? This function is known as the Shannon function and is defined as: \[S(n)=\max\{C(f) \colon f \in B_{n}\} \ .\] In this section, we will manage to establish the exact asymptotic behavior of the function \(S(n)\)!