---
Video Title: Big-O Examples
Description: Theory of Computation
https://uvatoc.github.io/week5

11.3: Big-O Examples
- Proving f(n) is in O(g(n))
- Proving f(n) is not in O(g(n))

David Evans and Nathan Brunelle
University of Virginia
---

Now let's look at the functions.

C was divided, whether this one was within
big O.

So C is a pretty tricky one.

The other one that was a little bit more
divided was E.

If you weren't sure about the others,
definitely try with the definition.

You should be able to prove by picking
values of C and 0.

So what about this one?

This one gets both at
understanding the definition

and being a little bit
comfortable manipulating logs.

For this to be the case, this is F of N or
F of S.

This is G of S.

So the question is, are
there constants where

it's less than... is
always less than that.

For all S greater than N is 0.

If we can pick the constants
that make this inequality

always true, that would
show that it is in big O.

If we can show that whatever the constant
is, we can always find some value of S

that violates the inequality, that would
show it's not.

What is log of S squared?

Can we simplify that?

Good.

Yeah.

So that is 2 log S.

Definitely your intuition that when things
are squared that might change the

asymptotic class, whether it's in big O,
is a good intuition.

Once things are inside logs, that's a bad
intuition.

Within a log, the inverse of exponential.

So doing a square within a log is not a
big deal.

For all practical purposes, and I think
the quote at the beginning of the chapter,

or maybe the beginning of the other
chapter, log is basically a constant.

Logs are small constants.

They matter because if the input's big
enough, the log does increase.

So it's not really a constant.

In this case, now we have that.

This is the equivalent of one-half S to
log S.

We can simplify that.

So what value do we need to choose for C?

Well, we can choose almost any value for
C.

This is going to work.

One is a good choice.

It would be obfuscating to pick a bigger
value, because it actually works for C

equals one, and it works for N zero equals
one.

So that is in big O.

So what about this one?

So this we should be able to answer very
easily from the definition.

For this to be in, we just have to find C
and N zero, write our definition.

So what do you want to pick for C and N
zero?

It's inequality, so we don't have to do a
lot of math to figure it out.

Let's pick N zero as 5000 and C as one.

Or we could pick N zero as 3102,
C as one.

So the one that wasn't was the squared.

Do you want me to do that?

How we would show that S squared is not in
big O, S, log S?

That I think people have the right
intuition.

Actually proving it to back up that
intuition I think is more difficult.

So the question was, is S squared in big
O, S, log S?

And in this case, it is not.

To satisfy the definition, it would have
to be the case that, so we have S squared

is less than or equal to C, S,
log S.

What value can I pick of N that would
violate that inequality?

So it can't be a constant, right?

So any constant I pick,
you can pick a C value

that's going to make
this inequality true.

So the value I pick has to be a function
of C and N zero in some way.

But this is the way within the for all and
there exists, I get to pick last.

You pick C and N zero, whatever you pick.

If I can pick an N that
makes the inequality false,

then I've shown that
it's not within the big L.

So it's probably some function of C.

The N zero just means, well, it has to be
higher than N zero.

But usually getting higher than N zero is
easier.

What function of C should it be?

First one we try, what if we just pick C?

Would that work?

Sorry, this is S.

I switch from S to N.

This should be S.

So that would mean C squared is less than
or equal to C times C log C.

Is that okay?

That looks true.

Is that satisfying what we need?

We want the inequality to be false.

Showing it's true, definitely does not
show that it's not in big O.

Showing it's true for some value,
it doesn't show that it is in big O.

To be in big O, it's gotta be true for all
values.

So that didn't work.

What else could we pick?

Yeah.

OK, we could pick C squared.

Good.

And you may think, oh, is that allowed?

C is a constant.

We can pick any function on C we want,
right?

We could pick 2 to the C we could pick C
to the C to the C.

We can pick anything you want,
because it's a constant.

So if you pick c squared and plug it in,
now we're going to get c to the fourth is

less than or equal to c times c squared
log c.

Our goal is for this to not be true.

So is it true that that's not true?

Yes.

And the reason it's true, well,
this is c cubed, and this is less than c.

Yeah, we've got to also pick greater than
n zero, but that's easy.

If this isn't greater than n zero,
we can just increase it until n zero.

Yeah, question?

Oh, you're right.

Sorry.

For this one, that's s.

This is less than c.

That is 2 log of c, which for some really
small c values is not less than c,

but for any interestingly big c value is
definitely less than c.

Good.