[SER222] Asymptotics (4/5): Tight Bounds

Summary

El guion trata sobre los límites superior e inferior de las funciones y cómo los límites ajustados (tight bounds) son útiles para modelar el comportamiento de programas. Se explica que los límites ajustados son cuando dos funciones se superponen y se convierten en idénticas a medida que el tamaño de la entrada se hace muy grande. Se introduce el símbolo 'tilde' para representar límites ajustados y se contrasta con 'big O', que arroja información. Además, se menciona el símbolo 'theta', que representa límites ajustados cuando una función es tanto big O como Omega de otra, aunque es menos común debido a su dificultad para ser demostrado.

Takeaways

• 📈 Los límites ajustados (tight bounds) son una forma de describir las relaciones entre funciones donde, para valores grandes de x, dos funciones se solapan y se comportan de manera idéntica.
• 🔢 Un ejemplo de límite ajustado es la relación entre las funciones x^4 + 2x y x^4, donde para valores de x muy grandes, ambas funciones se comportan de manera similar.
• 📚 El límite ajustado se representa con el símbolo 'tilde' (~) y se usa para mantener información sobre la función de crecimiento, incluyendo el coeficiente.
• ✂️ Para encontrar un límite ajustado, se eliminan todos los términos menos el término dominante, pero se mantiene el coeficiente.
• 📊 Para validar un límite ajustado, se toma el límite del ratio de la función original y la función límite ajustada, y si el resultado es uno, entonces la función límite ajustada es válida.
• 📐 La diferencia entre Big O y límite ajustado (tilde) es que Big O descarta el coeficiente, mientras que el límite ajustado lo mantiene, lo que puede ser útil para comparar funciones con diferentes coeficientes.
• 📉 El límite ajustado Theta (Θ) se usa cuando una función es tanto Big O como Omega de otra función, lo que significa que tiene límites superior e inferior que se encuentran.
• 🛑 Es difícil obtener límites Theta porque requiere que los límites superior e inferior sean iguales, lo que a menudo no ocurre en las funciones de crecimiento.
• 📖 Aunque Theta es popular en la literatura, es menos común usarlo en la práctica debido a la dificultad de demostrar que los límites superior e inferior son iguales.
• 🔄 La preferencia general es por el límite ajustado (tilde) porque mantiene más información y es más fácil de escribir y entender que Theta.

Q & A

¿Qué son los límites superior e inferior de una función?

Los límites superior e inferior de una función son valores que proporcionan una estimación de la complejidad de una función. El límite superior (O) indica el peor caso y el límite inferior (Ω) indica el mejor caso.

¿Qué es un límite ajustado y cómo se relaciona con las funciones?

Un límite ajustado es una función que se asemeja mucho a otra función a medida que el tamaño de la entrada se hace grande. Se dice que dos funciones están ajustadas si su relación se acerca a 1 cuando la entrada se vuelve muy grande.

¿Cómo se determina si dos funciones están ajustadas entre sí?

Para determinar si dos funciones están ajustadas, se calcula el límite de la razón entre ellas cuando el número de entradas tiende al infinito. Si ese límite es 1, las funciones están ajustadas.

¿Cuál es la diferencia entre un límite ajustado (tilde) y un límite superior (O)?

El límite ajustado (tilde) mantiene la información del coeficiente, mientras que el límite superior (O) lo descarta. Esto hace que el límite ajustado sea más preciso y conservador de información.

¿Cómo se determina el límite ajustado (tilde) de una función de crecimiento?

Para encontrar el límite ajustado de una función de crecimiento, se mantienen los términos dominantes y se eliminan los términos subdominantes, sin descartar el coeficiente.

¿Por qué es preferible usar límites ajustados (tilde) en lugar de límites superiores (O)?

Los límites ajustados (tilde) son preferibles porque conservan más información, lo que permite una estimación más precisa de la complejidad de una función.

¿Qué es Theta y cómo se relaciona con los límites ajustados?

Theta (Θ) es una notación que indica que una función está tanto en O como en Ω de otra función, es decir, es un límite superior y un límite inferior ajustado al mismo tiempo.

¿Cuál es la dificultad para encontrar una función que cumpla con la notación Theta?

La dificultad de encontrar una función que cumpla con la notación Theta es que requiere que el límite superior y el límite inferior sean iguales, lo que a menudo no ocurre en la práctica.

¿Cómo se representa la idea de 'error' en las funciones de límite ajustado?

La idea de 'error' en las funciones de límite ajustado se representa mediante el término 'a', que es una cantidad pequeña que puede variar y que se incluye en la expresión para indicar que se han eliminado términos no dominantes.

¿Por qué es importante mantener el coeficiente en el límite ajustado (tilde)?

Mantener el coeficiente en el límite ajustado es importante porque puede afectar significativamente la cantidad de trabajo que se tiene que hacer en una función, y por lo tanto, proporcionar una estimación más precisa.

Outlines

00:00

📈 Limitaciones y conceptos de funciones

El primer párrafo explica los límites superior e inferior de las funciones y cómo se visualizan. Se menciona la importancia de los límites estrechos y cómo se pueden representar gráficamente. Se usan dos funciones, x al cuadrado y x al cuadrado más 2x, para ilustrar cómo se superponen al aumentar el valor de x. Se enfatiza que el límite estrecho de x al cuadrado más 2x es x al cuadrado, y cómo esto se puede representar matemáticamente usando el símbolo tilde (≈). Se describe el proceso para encontrar límites estrechos eliminando términos no dominantes y conservando el coeficiente. Además, se menciona la importancia de los límites estrechos para modelar el comportamiento de programas y cómo pueden proporcionar una estimación precisa del trabajo que se debe realizar.

05:03

🔍 Detalles y diferencias entre Big O y Tilde

El segundo párrafo profundiza en la diferencia entre los límites superiores (Big O) y los límites estrechos (Tilde). Se explica que mientras Big O descarta información relevante como los coeficientes, Tilde los conserva, lo que resulta en una estimación más precisa de la función de crecimiento. Se proporcionan ejemplos para ilustrar cómo se calcula el límite estrecho para funciones específicas, como 2n más tres y log de n veces 35n al cuadrado. Se discute la preferencia por el uso de Tilde por su capacidad para mantener información valiosa y cómo esto puede afectar la comparación de funciones de crecimiento. También se menciona la relación entre Big O y Tilde, y cómo Big O puede representar términos fluctuantes usando la notación de límite.

10:03

🔗 Theta y sus implicaciones en la modelación de funciones

El tercer párrafo explora el concepto de Theta como un tipo de límite estrecho que requiere que tanto el límite superior como el inferior de una función sean iguales. Se explica que esto es difícil de lograr y que, en la práctica, los límites Theta rara vez existen porque es complicado hacer que los límites superior e inferior se toquen. Se discute la dificultad de demostrar que los límites de una función están lo suficientemente cerca como para cumplir con la definición de Theta. Aunque Theta es menos utilizado en la práctica, se entiende como un límite estrecho que sigue de cerca una función de crecimiento. Se menciona que, aunque Theta es más popular en la literatura, Tilde es más fácil de usar y entender.

Keywords

💡Límite

En matemáticas, un límite describe el comportamiento de una función cuando el argumento se acerca a un cierto valor. En el vídeo, se menciona el uso de límites para definir las relaciones entre funciones y para verificar si una función es un límite estrecho de otra, como cuando se habla de que la relación entre dos funciones tiende a uno cuando 'n' se hace muy grande.

💡Función

Una función es una relación entre dos conjuntos en la cual cada elemento del primer conjunto está asociado a exactamente un elemento del segundo. En el vídeo, las funciones son el tema central, donde se analizan sus comportamientos y cómo se relacionan a través de límites y límites estrechos.

💡Límite Superior

Un límite superior es una noción matemática que se usa para describir el comportamiento superior de una función. En el vídeo, se menciona cómo los límites superiores son una forma de modelar el crecimiento de funciones, pero suelen descartar información importante como los coeficientes.

💡Límite Inferior

Similar al límite superior, el límite inferior describe el comportamiento inferior de una función. En el vídeo, se discute cómo los límites inferiores ayudan a entender el crecimiento de funciones, pero igual que los límites superiores, pueden no ser lo suficientemente precisos.

💡Límite Estrecho

Un límite estrecho es una relación entre dos funciones que se acercan el uno al otro cuando el argumento se hace muy grande. En el vídeo, se explica que un límite estrecho es una forma de modelar el comportamiento de programas de manera más precisa que los límites superiores o inferiores.

💡Tilde (Límite Estrecho)

La tilde se usa para representar límites estrechos en la notación asintótica de funciones. En el vídeo, se explica que la tilde nos permite mantener información sobre los coeficientes, lo que resulta en una estimación más precisa del comportamiento de las funciones.

💡Dominante

Un término dominante en una función de crecimiento se refiere al término que tiene la mayor influencia en el comportamiento de la función cuando el argumento se hace muy grande. En el vídeo, se menciona que para encontrar límites estrechos, solemos mantener el término dominante y descartar los demás.

💡Coeficiente

Un coeficiente es un factor numérico que se multiplica por una variable en una función. En el vídeo, se discute la importancia de mantener el coeficiente en los límites estrechos, lo que nos permite tener una estimación más precisa del comportamiento de las funciones.

💡Alfa

Alfa se menciona en el contexto de límites estrechos como una forma de representar términos adicionales que no son dominantes y que se descartan en la notación asintótica. En el vídeo, se explica que estos términos Alfa pueden representar cualquier constante que no sea dominante.

💡Theta

Theta se refiere a una noción de límite estrecho donde tanto el límite superior como el inferior de una función se cierran en una misma función. En el vídeo, se menciona que theta es más difícil de alcanzar que la tilde porque requiere que los límites superior e inferior sean iguales.

Highlights

Introduction to tight bounds for functions

Visualizing tight bounds with two functions: x^4 and x^4 + 2x

Tight bounds occur when functions overlap as x gets large

Definition of tight bound: x^4 + 2x is tightly bounded by x^4

Tight bounds provide an accurate estimate for large values of x

Tight bounds are useful for modeling growth functions

Different ways to write tight bounds: tilde and theta

Tilde notation represents a function that is tightly bounded

Finding a tilde bound by dropping non-dominant terms

Example of finding a tilde bound for 2n + 3

Validation of a tilde bound using limits

Tilde bounds retain more information than big O bounds

Preference for tilde bounds over big O for retaining information

Graphical representation of big O and tilde bounds

Theta bounds require both upper and lower bounds to be the same

Theta is harder to achieve than tilde

Theta is less commonly used due to its complexity

Conclusion on the preference for tilde over theta

Transcripts

So, now that we have spent some time

understanding upper and lower bounds for functions,

let's talk about tight bounds.

So, tight bounds, we didn't really do it in our overview,

kind of picture of stuff.

So let's try to visualize this.

So, consider you have may be two functions

you have a x to the fourth and x to the fourth plus 2x.

So I have graphed that here in this picture.

The one that starts more kind of linearly,

this is going to be our x to the fourth plus 2x.

The one on the other side is going to be x to the fourth.

So I have two functions there.

Notice that when x gets reasonably large,

these functions overlap one another.

So they follow each other one to one.

Instead of one being substantially greater than the other

or substantially less than the other,

they kind of just seem to overlap.

They exactly follow one another.

This is what I would call a tight bound.

So the tight bound, x to the fourth plus 2x,

is x to the fourth.

As x gets really large, these functions become identical.

So this is what's called a tight bound.

So there's this little area in the beginning

where 2x has a little impactor, but once x gets

sufficiently larger, I guess past that x zero cut off point,

they become effectively the same.

So, one thought would be is that, hey, this would be

another way to model or understand growth functions.

We can hope to write a tight bound for it instead of

an upper bound or lower bound.

And this particular tight bound, generally speaking,

is gonna give me a pretty good estimate for exactly

how much work I have to do.

Now, it will be a little bit off because I'm forgetting

about that plus 2x term there,

but for very large values of x it'll be exactly the same.

So tight bounds are very nice when we can find them.

They'll let us almost exactly model how our program behaves.

So there are a couple different ways

that we can write tight bounds.

We're gonna do this first tilde and then,

on the next page, theta.

So tilde.

We'll literally write the following.

We'll write tilde f of n to basically represent a function

that is tight bounded.

What the tight bound means is basically if I have

two functions, f of n, g of n,

and I divide them in the limit, that the ratio will be one.

So as n gets really large, imagine we're taking the limit,

we'll use the limit that's in text down below.

As that n value gets really large, that ratio is one.

And what that represents is that those functions are

convergent on one another.

They're basically overlapping on our graph.

They are effectively the same, they are tight bound

of one another, f is tight bounded by g.

So how do we actually find a tilde?

How do we find this bound?

Well, if we have a growth function

it's actually really easy.

For a growth function, all we do is drop all but the

dominant terms.

So it's actually less work than trying to write

for a big O expression.

In big O, we dropped all but the dominant term

and then we dropped the coefficient.

Here we leave the coefficient in place.

So, looking down, we actually have some examples.

So here I have my f of n, and these are actually

the same as what we did for big O.

So we have 2n plus three as our first one.

In this case I'm trying to find out what the tilde is,

what is the tight bound for it?

I keep the dominant term and drop everything else.

So in this case I keep 2n.

So, this over here is saying that g of n are tight bound

is equal to 2n.

So, tight bound over here.

Original function over here.

Now, if I want to validate that, I have to basically

take a limit.

Before when we did some algebra,

we had to figure out some constants.

Here it's almost easier depending on how hard it is

for you to value them.

Basically what happens is that we need to check

the ratio of them.

So the ratio g of n over f of n.

Here I'm saying the limit of 2n over 2n plus three.

Of course I'm taking the limit as n gets really large.

We said earlier that we want to take a look at our programs,

at our growth functions when n is really large.

For programs that are so large that there's no kind of

special behavior happening as we go between the small ns.

No special overhead, no special cases.

So let n be really large.

So now what we do, let's say we used that process

to determine that g of n, here we've determined that

tilde, the tight bound is 2n and we want to verify it.

All I really do is take that limit of the ratio

and evaluate it.

So I take that there and I see what it's equal to.

If it's equal to one then I'm good.

Those things follow each other exactly in the limit

so that is a valid tight bound.

So here I'm not gonna work through the algebra doing that.

It's pretty simple though.

I really wouldn't expect you to do

the algebra yourself either.

As long as you set it up, you can probably put it into

something like a CAS, a Computer Algebra System,

and it will compute the answer for you.

So our second example here is for f2.

f2 is a little more complicated.

This is log of n times 35n squared.

If we wanna find the tilde for that,

we drop all but the dominant term and then

leave that term alone.

So here we drop this, over here we drop the three

and we're just left with 2n.

Here we don't have a coefficient so there's no extra

information that we keep by leaving it alone.

For this big O we're just throwing away

that coefficient here.

In tilde we keep it but if it's not a coefficient

it doesn't really matter.

Again, if I wanna show whether or not that's valid,

I basically take the limit as n approaches infinity,

I would ratio those two functions.

If it's equal to one then I'm good to go.

And these two limits here, if you want to value them,

they will work out, they will value to one.

So we should be good to go.

So, there we have it.

So that's our tilde bounds for both f1 and f2.

At this point we have several different ways

to characterize a function in terms of bounds.

My general preference is gonna be for tilde.

At least in terms of big O.

So big O is an upper bound, but big O we are basically

throwing away information.

We threw away not just all the lower terms

but the coefficient as well.

Tilde is keeping that information.

Tilde is retaining that number in front.

And that is really valuable

because that number could actually matter.

We can imagine if we have two functions,

maybe we have an f of n, one under n versus f of n one of n,

those two functions, in terms of big O, o of n

in terms of big O are gonna look the same.

Big O is gonna be o of n.

So if I have here, let me actually draw this,

so I have an f of n equal 100n.

And f of n equal 2n.

In terms of big O, these things are the same.

These are both gonna be big O of n.

This basically is throwing away the fact that

one of them is 50 times lower than the other.

And I don't like that.

In tilde, we would have maybe tilde of 100n

versus tilde of 2n.

We keep that coefficient.

In that case I can clearly see how different

those things are.

So for me I prefer that tilde because I'm not

throwing away information.

The only issue is that tildes can be harder to write

because you need to have that coefficient in front.

If anybody does some of the empirical analysis that we did,

we may have a value in front, but it's kind of questionable.

It's super specific to the system or something.

But if we have it, I really think we should keep it.

Now, as a final note here, I have a remark here

based on big O.

Here we're saying we gave a prospect for determining

the g of n in a tilde.

Now g of n is literally just a term for the

original growth function.

It's a particular mathematical term.

What we can think of is the following.

My f of n, my original function, this over here.

That is really g of n, the tight bound,

that first term plus air.

So tilde, we say throw away all but the dominant term.

So, in this case, my dominant term is lineal,

it just has n in in it,

versus my other term is constant time.

Well basically what that means is we can say,

think of this as f of n is g of n, our 2n

plus some air, plus o of one air.

O of one is basically a little quantity that

kind of can vary a little bit.

Basically what we are saying is that the air

in that expression is upper bound on some constant.

That may be a little bit awkward to think about

but big O, when we write it in a mathematical expression,

and we won't do it often in this course,

usually we just say it equals f of n is bound recently,

but when we use o of n by itself, what that is representing

is a bit of a term that can fluctuate.

So, in our tilde expression, why we threw away that constant

our term that wasn't dominant, we're really writing

power to two is a three, but we just threw it out.

And the way that we can represent that we threw it out

is by saying that there is an o of one air there.

I'm using the word air basically whenever I have

o of n in a normal expression to represent that

o of n is kind of a bound.

There's tons of things that could be under it.

An upper bound is basically representing that

they have this mystery function that hides underneath it.

Here I could be hiding four or five or six.

I threw away whatever constant was added on there

so it could have been any of those.

And the way I can represent that is actually using big O.

The next line there I have is similar example

where it says f of, actually it should be f2,

that thing is really g2 plus an air on log, log of n.

'Cause I kept the dominant term

and I threw away the log term.

So that gives me a little bit of air.

Okay, so let's take a look at some more.

So tilde's really nice because it keeps a lot of detail.

Maybe you don't have to worry too much

about that relationship with big O

but just know that it contains more information.

It's a tighter bound.

Now let's take a look at one more method we can use

to tightly bound something.

And that's called theta.

So theta goes back to our definitions of big O and Omega.

So basically what we say is that a function is tight bounded

by g of n.

So we have this over here, f of n.

f of n is tight bounded by g of n, state of g of n

when this holds.

f of n equals theta of g of n if and only if

f of n is big O of g of n and if n is Omega of g of n.

So when our upper bound and our lower bound are the same

well then my theta holds.

Now the issue here is that it's rather hard

to get both upper and lower bounds to look the same.

So if you think about what we've talked through,

you can think about maybe our upper bounds are gonna look

something like n, our lower bounds will look

something like ten.

It's hard to make those convert.

So a lot of times our thetas don't really exist

because they require to bring

our upper and lower bounds together.

So when I think about this graphically,

normally it's something like this.

Where this is maybe my f of n.

This is my upper bound, I'll call it a.

My lower bound, I'll call it b.

And the problem is, is normally a and b diverge.

Those functions go their own way.

Sure a is an upper bound for f, b is a lower bound for f

but a and b don't ever meet up again, they diverge.

The problem with this definition is it basically is saying

that you have to bring these in.

And it's gonna be extra work for you to prove

that our o of n and Omega are really close together.

That they are the same.

And only once you've done that, once you've brought in

those two functions as tight as possible,

get them as close to that f of n as possible,

are you allowed to say that that f of n

has a tight bound that's equal to a and b.

That they compress together on that line

and once they meet up that they enforce a tight bound,

that they enforce a theta bound.

So this is a little bit harder to do

than some other things.

Again, this is gonna be something we almost never use.

For us, the way we think of it, is that theta is basically

a tight bound.

So it's another function that closely follows

a growth function.

For us though, we'll mainly use tilde

just because it's gonna be a little easier to write,

a little easier to think about.

Theta is more popular in literature.

It's maybe something you hear people talking about

but it's just so hard to get.