---
Video Title: Understanding the Asymptotic Operators
Description: Theory of Computation
https://uvatoc.github.io/week5

11.2: Understanding the Asymptotic Operators
- Quiz (answers in next video)
- Functions where f(n) \notin O(g(n)) and g(n) \notin O(f(n))

David Evans and Nathan Brunelle
University of Virginia
---

So here are five functions.

For each of these, your question is,
is that in the set big OS log S?

See if you can answer this based on your
current understanding of it.

So the one that has the most yeses is this
one, actually.

C is about evenly split.

I guess this confirms that
there's enough confusion

about this that it's good
that we're recapping it.

These two, there's high confidence.

Our intuition and the definitions tell us
that 2S grows no faster than S log S,

asymptotically.

2S log S, so these two should be equal,
but we're still going to look at the

definition because our intuition can fail
us.

There is some disagreement about the best
way to define what big O means.

This is the definition that
we used last class and

the one that we will
use throughout this class.

This is the definition that says we're
defining big O.

It's defined as a set of functions.

And what that set is depends on the
function that is inside the O.

In order to be in that set, it has to be
the case that we can find two constants.

One is positive, one is a natural number,
so it could be zero.

It's not required that n zero is positive.

Such that this property holds.

That f of n, which is the
function that's in the set, is

always less than or equal
to that constant times g of n.

For all the numbers greater than n zero.

We'll look at the examples, but first make
sure we understand that definition.

So if we want to prove
that some function is

within some big O set,
what do we need to do?

What's the most likely way to prove that?

Yeah.

Good.

Definition is that there exists.

The easiest way to prove that there exists
is to construct it, to find them.

Right?

So if we can find choices of c and n zero
and then show inequality holds,

this is exactly the inequality from the
definition, then we're done.

So all we've got to do is find those two
constants and have an argument that is

convincing that that inequality always
holds for those choices.

But usually once we've
chosen c and n zero, showing

that it always holds should
be pretty straightforward.

This is just an inequality.

That's proving it is in.

What if it's the case that now f of n is
not in big O, g of n?

Proving that something
doesn't exist is

usually harder than
proving that it does exist.

So how can we prove not in?

There are things that we could define that
is the complement of this.

That is a good strategy to say,
well, let's define something that is the

set of the complement of this,
right?

To get the opposite of this definition.

And if you can prove
that you're in that opposite

definition, that would
prove you're not in this one.

But you'd have to be pretty careful about
how to define that.

It's not just flipping the inequality.

What's another strategy we could use to
show something doesn't exist?

Yeah.

So if we want to get
a contradiction, what

would we need to do
to get a contradiction?

Two things to look at.

This there exists.

To get a contradiction to there exists,
we have to say for all.

To know that there do not exist those two
constants, we have to show for all

possible choices of those constants,
that inequality is not satisfied.

That means what we're
really showing is that for

all choices of c and n0
that satisfy these rules.

For all those choices, what do we have to
show exists?

Yeah, look at that.

Good.

The hard part is the for all c and n0.

But once we've done that,
all we've got to do is find

some n such that f of n is
now greater than c of g of n.

And this has to be an n greater than n0.

So that's where the there exists helps us.

We've just got to find one n that
invalidates the inequality because the

inequality has to hold for all n greater
than n0.

Those are our main proof strategies.

Let's test this definition.

I think it gets at this
question of what would

happen if we just tried
to flip the inequality.

So are there any two functions?

Two functions, f and g. And the question
is, is it ever the case that we can find

two functions where f is not in big O,
g of n, and g is not in big O of f?

So if we think of the definition being
flipping the inequality, that should be

our intuition would say that's not the
case.

Out of this context, a less than or equal
to, you've got two numbers, either that a

is less than or equal to b, or b is less
than or equal to a.

One of those two has to be true.

Maybe both are true.

If we just use our intuition about this
sort of means grows no faster than,

our intuition would tell us one of those
two has to be true.

Can you think of any functions where it's
not true?

This is a perfectly good function.

Is that a perfectly good function?

Let's try another perfectly good function.

Is the blue one, big O, the purple one?

In the big O set for the purple one?

So if the points that are discontinues,
the points where it's zero.

If those are the same, then would you say
the blue is big O, the purple?

Let's say this is zero, this is a
thousand.

Actually, now they're the same function.

If they're the same function, they're
definitely within big O of each other.

How can I change the functions so now
they're not within big O of each other?

In either direction?

To prove not, all you
do is pick one n that

violates for whatever
choice of n0 and at c.

One way to think of these for all and
exist is kind of adversarial.

Like someone else gets to pick n0 and c.

Whatever they pick, you can pick an n0
that violates the inequality.

Good.

Yeah.

If we change it so they're not zeros in
the same place, we're going to say this is

going to be zeros, let's say at a thousand
and one.

Then for the points that
are divisible by a thousand,

the purple function is
always going to be higher.

Whatever choice of c and n0, well, we can
find some point above n0 where it's higher.

And the choice of c doesn't matter because
the other one's zero.

But in the other
direction, well, we just find

the point that corresponds
to a thousand and one.

And that's going to always be greater on
the blue function.

And these are not the kinds
of functions you're normally

happy to deal with, but
they're perfectly good functions.

There's no requirement
that a function can't

have points that it
behaves strangely at.

So there are functions like this.

One of the alternate definitions of big O
would say this is kind of silly.

To say because of these like sparse
points, all of a sudden we can't say

anything interesting about these functions
is kind of bad.

The definition that is
sometimes used is instead

of this, it's used for
all but a finite number.

Inequality holds for all but some finite
number of points.

Does that actually solve the problem here?

Yeah, it doesn't solve the
problem here because there's

infinitely many points where
the inequality doesn't hold.

At least in this case,
it makes the definition

more confusing and doesn't
even solve our problem.

The intuition that it just means grows as
fast as is usually useful.

Sorry, grows no faster than for big O.

But the definition is more precise than
that and doesn't always capture that.