---
Video Title: Using Big-O (Theorem 5.2)
Description: Theory of Computation
https://uvatoc.github.io/week5

11.1: Using Big-O (Theorem 5.2)

David Evans and Nathan Brunelle
University of Virginia
---

Our main goal today is to get to the
theorem that is Theorem 5.3 in the book.

That is actually a big and important
result, but the proof of it should be

something that all of
you understand, that is

basically building on just
being able to count things.

So we will get to that theorem that says
there are some functions that cannot be

computed without big circuits,
which is a pretty important theorem.

So this is Theorem, slightly reworded,
what's Theorem 5.2 in the book,

which is actually kind of strange,
the way it's written.

So it's a theorem that says, for every
natural number s, so we define size of the

set of all functions
that can be computed

with a NAND-CERC
program of at most s lines.

So this is kind of analogous
to counting the number

of NAND gates, but it's
not exactly the same as that.

It's very precisely defined here that
we're counting lines in a NAND-CERC

program, and we have defined what a
NAND-CERC program is.

So what the theorem is saying is for every
natural number, the number of functions

that can be computed by a NAND circuit of
that size, size of s is a set of

functions, and we're
counting the size of that, and

we're saying it's less
than 2 to the big O s log s.

So if you remember well what Nathan
presented about what big O means,

this should really bother you.

Because what is that actually saying?

What is big O s log s?

It is a set of functions.

Does that make any sense to raise a number
2 to the power of a set?

Something wacky is going on here.

This definitely does not mean what it
says, if you interpret it literally.

The notation that tends to get used,
this is a set of functions.

It doesn't make any sense to raise up 2 to
the power of a set of functions.

It's a type error.

It doesn't make any sense.

So this notation, actually, there's a lot
implied in this way of using the notation

that people kind of accept
without really reading it

carefully and trying to
figure out what that means.

So what do we think it actually means?

What is the exponent in that power?

Because it can't be a set of functions.

So what is the cardinality of...

Let's do an easier one first.

What's the cardinality of the set big O 1?

How many functions are there?

We'll use your intuitive notions that they
grow no bigger than a constant.

How many functions are there?

There are infinitely many.

And we won't try to answer now whether it's
countably infinite or uncountably infinite.

So these are definitely infinite.

So that definitely doesn't make sense as
the exponent either.

Especially, it better
not make sense if it's

infinite and we've got a
less than or equal to here.

Because, well, I guess it would be
everything, right?

It wouldn't be an interesting number.

So what else could it mean?

Yeah.

So there's got to be some
kind of hidden implication

here that we're finding
some function in this set.

It could be something like this.

Or maybe it's a for all.

Which one of these do we think it's going
to be?

Which one of these two should it be?

Should it be there
exists some function in

that set, or for all
functions in that set?

What are examples of functions of this big
O S log S set?

Is the function... is that in that big O S
log S set?

Yeah.

The function that always outputs one is in
that set.

If this is going to mean
something, or if this is correct,

this is definitely not correct
for all functions in that set.

This is a function that's in that set,
that two to the one is two.

This is definitely not less than or equal
to two for all S.

So it can't be for all.

It better be there exists.

What's hidden in this statement,
if we think of it more carefully,

and the way this is actually in the book,
there's a little footnote there that says

we actually know the
constant, and instead

of the big O, we could
put 10 or something.

Specific function that exists that
satisfies this.

So what does it say?

There exists some function in this big O
such that this is true for that F.

But it's also, we have
to be a little careful,

because the big O is
for all n greater than n0.

So it's not for all n that that happens.

So this is a pretty weird way of stating
what could be a simpler set theorem,

but it's more, at least it's viewed by
people that get really comfortable and

maybe more comfortable than they should
with asymptotic notation as more

convenient and proper
than just saying, let's pick

this function that we know
works, that is in that set.

But that's what must be implied by the way
this definition is written.

So