[SER222] Asymptotics (2/5): Upper Bounds

Summary

En este video se explica la idea de una cota superior utilizando funciones matemáticas. El presentador muestra cómo graficar funciones para entender cuándo una función es mayor que otra más allá de un punto específico, llamado x0. Se introduce la notación de Big O, que define formalmente las cotas superiores para analizar el tiempo de ejecución de algoritmos. A través de ejemplos, se explica cómo eliminar términos no dominantes y coeficientes para encontrar el Big O de una función, destacando la importancia de aproximar la cota superior lo más cercana posible a la realidad.

Takeaways

• 📊 La función g(n) parece ser una cota superior para f(n) después de un punto específico llamado x0.
• 📝 La notación f(n) = O(g(n)) indica que f(n) tiene una cota superior en términos de g(n).
• 🔢 La definición matemática de cota superior dice que |f(n)| ≤ C * |g(n)| para n > x0, donde C es una constante.
• 📈 Al graficar, g(n) siempre está por encima de f(n) después del punto de intersección x0.
• ⚖️ Para encontrar la cota superior (O grande) de una función, se eliminan los términos no dominantes y las constantes.
• ✔️ Un ejemplo: f(n) = 2n + 3 tiene O(n) ya que el término dominante es n.
• 🔍 Se puede demostrar formalmente la cota superior al encontrar un valor de C que satisfaga la relación matemática.
• ⚙️ El proceso para determinar la cota superior de una función implica simplificar los términos y aplicar la definición de O grande.
• ⏲️ El uso de constantes en las cotas superiores da flexibilidad, permitiendo ajustar la función g(n) para que sea una cota válida.
• 🔢 En términos de logaritmos, todas las funciones logarítmicas tienen la misma cota superior debido a la conversión constante de base.

Q & A

¿Qué es una cota superior en términos de funciones matemáticas?

Una cota superior es una función que siempre está por encima de otra función a partir de un cierto punto. Esto significa que, a partir de ese punto, la función g(n) es mayor o igual que f(n).

¿Cómo se denomina la notación para expresar una cota superior?

La notación utilizada para expresar una cota superior es O grande, que se escribe como f(n) = O(g(n)), lo que significa que f(n) está acotada superiormente por g(n).

¿Qué significa x0 en el contexto de la cota superior?

x0 representa el punto de intersección a partir del cual la función g(n) siempre es mayor que f(n). Es el punto a partir del cual la cota superior es válida.

¿Por qué es importante el valor constante C en la definición de cota superior?

El valor constante C permite ajustar la función g(n) para que sea mayor que f(n) en todo momento. Da flexibilidad en la definición de la cota superior al permitir escalar la función g(n).

¿Cómo se determina la cota superior de una función f(n)?

Para determinar la cota superior, se eliminan todos los términos menos el dominante y luego se elimina el coeficiente de ese término. Esto proporciona una estimación del crecimiento máximo de la función.

¿Cuál es el procedimiento para probar que una función f(n) está acotada superiormente por g(n)?

Para probar que f(n) está acotada superiormente por g(n), se demuestra que f(n) ≤ C * g(n) para un valor de constante C y para n mayor que x0. Esto implica resolver una desigualdad que muestre que la función cumple con la definición formal.

¿Qué es un término dominante en el análisis de la cota superior?

El término dominante es el término de la función que crece más rápido a medida que n aumenta. Es el término que determina el comportamiento de la función para grandes valores de n.

¿Por qué los logs en diferentes bases pueden considerarse equivalentes en términos de O grande?

Los logs en diferentes bases son equivalentes en O grande porque el cambio de base es una operación constante, y esta constante se puede absorber en la constante C de la definición de cota superior.

¿Qué papel juegan los valores absolutos en la definición formal de la cota superior?

Los valores absolutos garantizan que solo se considere el crecimiento positivo de las funciones, ya que el tiempo o las operaciones no pueden ser negativas. Aunque matemáticamente se incluyen, en la práctica no afectan mucho el análisis.

¿Qué ocurre si una función tiene más de un punto de intersección con su cota superior?

Antes del punto x0, las funciones pueden cruzarse varias veces, pero la cota superior solo se asegura a partir de x0, donde g(n) siempre es mayor o igual que f(n). Las fluctuaciones antes de x0 no afectan la cota superior.

Outlines

00:00

📊 Introducción a la noción de cota superior

En este párrafo, el presentador introduce el concepto de una cota superior usando dos funciones arbitrarias, f(n) y g(n), representadas en un gráfico. Observa cómo g(n) parece ser mayor que f(n) a partir de un punto específico, x0, lo que sugiere que g(n) podría ser una cota superior de f(n). Sin embargo, aclara que, sin una definición matemática formal, esto es solo una suposición basada en la gráfica.

05:02

✏️ Definición matemática de la cota superior

Se presenta la definición formal de una cota superior utilizando notación matemática. f(n) es O(g(n)) si existe un constante C tal que el valor absoluto de f(n) es menor o igual que C veces el valor absoluto de g(n) para valores de n mayores que un punto específico x0. La importancia de esta definición es garantizar que f(n) no sobrepase a g(n) para grandes valores de n, manteniéndose dentro de los límites de la cota superior.

10:03

📉 Ejemplo básico de cálculo de O(f(n))

Este párrafo explica el proceso para calcular la cota superior de una función. El ejemplo f(n) = 2n + 3 ilustra cómo se descartan los términos no dominantes (en este caso, el +3) y el coeficiente del término dominante (2n), resultando en O(n). El proceso se valida utilizando la fórmula matemática y se explica cómo escoger la constante C adecuada para probar que la cota superior es válida.

15:05

🧮 Ejemplo con una función logarítmica

Aquí se muestra un segundo ejemplo utilizando una función más compleja, f(n) = log(n) * 35n². Se siguen los mismos pasos para determinar que la cota superior es O(n²). Nuevamente, el proceso matemático para probar que esta es la cota correcta implica verificar la definición formal y determinar un valor adecuado para C, garantizando que la función no sobrepase su cota superior para grandes valores de n.

🔍 Notas finales sobre las cotas superiores y los logaritmos

Se concluye con una explicación sobre cómo los logaritmos de diferentes bases (por ejemplo, log base 2 y log base 10) resultan en la misma cota superior. Esto se debe a que la conversión entre bases logarítmicas es una operación de tiempo constante, que queda absorbida dentro del valor constante C en la definición de la cota superior. En términos prácticos, esto significa que todas las funciones logarítmicas tienen la misma cota superior en el contexto de O(g(n)).

Keywords

💡Cota superior

En el video, la cota superior se refiere a una función que limita a otra desde arriba, lo que significa que una función f(n) nunca crecerá más rápido que una función g(n) a partir de un punto determinado. Esta idea es clave en el análisis de algoritmos para comprender el comportamiento de la complejidad de una función.

💡f(n)

f(n) representa la función que se quiere analizar en términos de su crecimiento o complejidad. En el video, f(n) es la función 'roja' y su comportamiento es comparado con g(n) para determinar si g(n) actúa como una cota superior.

💡g(n)

g(n) es una función arbitraria usada como referencia para comparar con f(n). Si g(n) siempre está por encima de f(n) después de un punto x0, entonces g(n) se considera una cota superior de f(n). Esta comparación es esencial para determinar la eficiencia de un algoritmo.

💡Punto de intersección (x0)

x0 es el punto a partir del cual g(n) se convierte en una cota superior de f(n). Antes de este punto, f(n) puede comportarse de manera impredecible o fluctuante, pero a partir de x0, g(n) siempre estará por encima de f(n). Este concepto es crucial para determinar dónde comienza a cumplirse la cota superior.

💡O grande (O(f(n)))

El O grande es una notación matemática usada para describir el límite superior de una función, es decir, la velocidad máxima de crecimiento de una función. En el video, se explica que si f(n) = O(g(n)), entonces f(n) está acotada superiormente por g(n) a partir de x0.

💡Constante C

La constante C es un factor de escala en la notación de O grande que permite ajustar la función g(n) para que sea suficientemente grande como para actuar como una cota superior para f(n). En el video, se menciona que C no está fija, lo que da flexibilidad para elegir un valor que haga que la desigualdad se cumpla.

💡Crecimiento

El crecimiento de una función se refiere a cómo cambia su valor en relación con n. El video compara f(n) y g(n) para determinar cuál crece más rápido, y así establecer si g(n) es una cota superior. Esto es esencial para el análisis de algoritmos y su eficiencia.

💡Termino dominante

El término dominante en una función es el que más contribuye a su crecimiento a medida que n aumenta. En el video, para determinar la cota superior, se ignoran los términos menores y se trabaja solo con el dominante, ya que este define el comportamiento asintótico de la función.

💡Coeficiente

El coeficiente es el número que multiplica a la variable en un término de una función. En el análisis de O grande, se ignoran los coeficientes al buscar la cota superior, ya que no afectan el comportamiento asintótico de la función.

💡Logaritmo (log n)

El logaritmo aparece en el video como parte de una función cuyo crecimiento es más lento que el de otras funciones polinómicas. En la notación O grande, los logaritmos de diferentes bases son considerados equivalentes porque las diferencias entre ellos solo involucran constantes, que pueden ser absorbidas por la constante C.

Highlights

Introduction to the concept of an upper bound using two functions, f(n) and g(n), with a graphical demonstration.

Explanation of how g(n) is an upper bound for f(n) past a specific point, referred to as x0.

Definition of Big O notation: f(n) = O(g(n)) represents that f(n) has an upper bound of g(n).

Mathematical definition of Big O: f(n) is less than or equal to a constant C times g(n) for n greater than x0.

Emphasis on dropping non-dominant terms and coefficients to simplify determining Big O for a given function.

First example with the function f1(n) = 2n + 3: The Big O is determined as O(n) after dropping the constant and coefficient.

Introduction of C as a constant used to adjust and scale g(n) for Big O calculations.

Second example: f2(n) = log(n) * 35n^2. The Big O is determined as O(n^2) after eliminating the non-dominant term.

Step-by-step demonstration of proving the Big O bound for a function using algebra and substitution.

Explanation of why logarithmic functions with different bases can have the same Big O due to constant time conversion.

The idea that Big O provides a worst-case time complexity and allows flexibility in adjusting constants to ensure f(n) remains bounded.

Emphasis on the importance of a 'tight' upper bound, avoiding unnecessarily large upper bounds like O(2^n).

Graphical interpretation of upper bounds, showing how g(n) must remain above f(n) past a certain point (x0).

Final note on how all logarithmic functions with different bases resolve to the same Big O due to constant time conversions.

Practical takeaway: the process of simplifying and proving Big O bounds is essential for analyzing algorithm performance.

Transcripts

- In this video, I want to elaborate

on the idea of an upper bound.

So, we only introduced the basic idea,

but we're gonna talk through this

with some mathematical notation.

So, take a look at the graph on the right-hand side.

There, I have two arbitrary functions,

one of them is red and one of them is blue.

Let me go ahead and label them.

So the red one, I'm going to call that my f of n.

So maybe this is somehow the function I'm trying to bound.

Then over here is the function,

I'm gonna call it g of n.

G of n is kind of another typical function name, right,

so we'll just stick with g of n.

So we have f of n and g of n side-by-side.

Now if I'm looking at this graph we see a trend.

That trend is that g of n is going to be,

past a certain point, always larger than f of n.

So this is basically our demonstration,

our graphical demonstration of the idea that g of n

is probably an upper bound f of n.

Now of course from this picture I don't know for sure.

Right, presumably these functions go on forever,

and right now I don't really have the evidence

to say g of n is for sure an upper bound on f of n.

In fact, right, if we think about mathematical terms,

well, we haven't even looked at a definition

for what something means to be an upper bound,

so we don't really know for sure,

but graphically we can kind of get an idea

of what is maybe happening.

So g of n appears to be past a certain point

always be higher than f of n.

Now that particular point we'll actually give it a name,

so that we'll call x sub zero.

So this little intersection here.

Right, so these functions intersect a couple times, right,

and there's sometimes that blue is greater than red,

red is greater than blue,

but past this particular point,

past this x0 point, our g of n, right,

our blue function is always greater than,

or appears to be always greater than f of n, alright?

So this is kind of our last kind of point of intersection,

it's going to be a particular point

past which our upper bound idea holds.

Right, so upper bounds are always going to be expressed

in terms of well, they are good past this point.

Prior to that point, I don't really know.

The idea being is that all sorts of different things

could happen with very small programs,

maybe you have some constant overhead,

and that initial region right before this x naught,

or x0, right, this region over here,

my analysis is basically gonna be

unpredictable because of all these little fluctuations

that happen, right, or special cases that happen,

so I don't really want to mess with that stuff.

Alright, so graphically this is the idea of an upper bound,

right?

We have my g of n always above f of n, past some region.

So how do we define that mathematically?

So now we're gonna get our hands a little bit dirty.

So I have a definition here, and I'm going to read it.

Definition.

We write that f of n equal O of n,

right, and this is basically the proper syntax,

f of n equal O of g of n to say that f of n

has an upper bound, right, keywords there,

of g of n.

In general, whenever I write O of n,

we're basically saying, oh,

the thing on the left, right, f of n, has some upper bound,

and then inside that O of n, right, the stuff in here,

right, this is what's actually upper bounded by, right?

G of n is just an arbitrary function, right?

It could be anything in there, right?

Could be n, it could be n squared, it could be whatever.

For now we're just saying it's generic.

Now when we say where we're upper bounded,

if we want to be more precise,

we'll say that f of n, right,

will take at most this number of operations, right?

It won't ever take more time than what that upper bound is.

We don't want that red line going above the blue line.

That would be against kind of our intuition

for what does it mean for something to be an upper bound.

And formula we'll see is the following:

f of n equal O of g of n if and only if

the absolute value of f of n is less than or equal

to a constant C times the absolute value of g of n,

for n greater than x0, where x0 is some constant.

So that'd be our formal definition.

Recall x sub zero from our previous slide

is that cutoff point, right,

at which point the upper bound actually holds.

Before then, anything could happen,

after it then we're good.

So our main definition lies here.

F of n equal O of g of n if and only if.

So mechanically, we're saying, right,

is that f of n is big O, right?

That's kind of our term for an upper bound.

We'll say that it's big O, that's the common nomenclature.

If, right, this right-hand side holds, right?

This absolute value of f versus the absolute value of g.

Our lesser values don't really matter to us all that much.

Remember that these are supposed to be growth functions

that we analyze, right?

And it doesn't really make sense for a function

to take negative time, right,

or negative number of operations,

so in general we don't really worry

about those absolute signs,

although in the mathematical kind of definition,

it's stating they are there

and so we should leave them there.

They just don't really complicate things for us

in the practical world.

And so what that bit of text there is saying, right,

is that f is upper bounded, right, by g of n,

if f is always less than some constant times g of n, right?

So g of n basically is some other arbitrary function, right?

And then that function, right,

basically is growing as fast as f, right?

We don't want f to somehow jump up in that graph

and spring over blue, you know?

The upper bound function, we don't want that to happen.

So g of n is basically obligated

to always be above f of n.

Now there's this little C value in there.

That C value is a constant.

Basically what that's saying is in our big O, right,

somehow our big O is some function,

it could be n squared, right,

I'm actually allowed to have some constant in front of there

that I can use to scale it.

I can use to make it bigger, right?

That coefficient, basically I'm allowed to play with it.

Notice that C isn't assigned a particular value here,

so allowed to basically change.

So it's somehow a little bit of flexibility

when we're writing an upper bound, right?

So you can maybe picture that blue line, right?

Maybe it could go up even higher,

or maybe it could even come down a little bit.

I'm allowed basically in the definition

to pick whatever coefficient I have in that function

that I use for my G of n, right?

I don't have to care about specifically what it is,

I'm allowed to pick something that's convenient.

So if I want to I can make it really big,

and maybe then it's easier for me to show

that a particular g of n is actually

the upper bound for an f of n.

So that's actually quite nice in terms of the math, right,

it gives us a little bit of flexibility.

And then of course, x sub zero is that fixed point

after which my upper bound is actually supposed to hold.

So that's our upper division.

So now let's take a look at how I would actually

go to a function and figure out what is the big O for it,

right, what is the upper bound for it.

So the process is pretty simple.

Basically say is given some function f of n,

drop all but the dominant term,

and then drop the coefficient

on the term that's left over.

So basically we're just throwing away a lot of stuff.

The result from that will be the big O

upper bound for that particular function.

Below I have a couple of examples.

So let's say over here

that my f of n is 2n plus three.

Well, try to find our rules.

First thing we want to do is drop all but the dominant term.

Here that 2n is the dominant term because it grows.

The plus three is just a constant,

it's not gonna do anything.

So we drop this plus three.

And then we have 2n, while our second part of our rule there

for finding big O, right, for finding separate bound,

is going to be to drop the coefficient,

so I'll drop the two.

Result is that our big O of f1 is n.

So over here, right, g of n, right, is equal to n.

Right, so, maybe if I had to write the full syntax here,

right, f1 of n is big O of n, right?

You remember generically, before we said that f of n

was big O of g of n,

but now we know what g of n is, right?

It's just n, so I can do substitution there.

So f1 of n, right, is O of n, right?

So that function there, right, 2n plus three,

is upper bounded by n, right?

By g of n equal to n.

So it's a linear function being bounded

also by another linear function.

Now of course the reason why that works

is because there's that free constant

we're allowed in front of n, right?

So I can actually pick something like, oh hey,

in g of n, right, that n maybe has a 10 in front of it.

Well, if I have 10n versus 2n plus three,

well, for decently large values, right,

that 10n is gonna be much larger than 2n.

So for sure that's gonna be an upper bound

that works for us just because we're allowed

to pick that constant there.

Now, if I wanted to prove that mathematically,

I would basically need something like this over here.

And it's really simple here for this example,

just because we're using a simple function,

but what we need to do do if you want to actually

prove that that bound is correct, right?

Initially, what we talked through

is kind of the heuristic process

for figuring out what is the big O of a particular f of n,

but what if I wanted to actually prove, right,

that that particular bound is correct?

What happens is that then I need to show

that that definition up top holds.

So that definition, right,

was something like, you know,

f of n less than or equal to g of n.

Right, so what I would do, right,

is basically try to show that these things work out.

And basically there's some substitution stuff that happens,

right, so over here I have my left-hand side, right,

is supposed to be absolute of f of n.

Here, right, my f of n was 2n,

plus three,

and then this is less than,

so let's assume these would sort of be absolute bars here,

let me make this a little more obvious.

Less than, and c times g of n.

So c absolute value g of n we said is n over here,

close that absolute.

Right, so if I were to just do that substitution,

based on my f of n and my g of n

that I got from that basic process that was defined,

they have this expression like this.

And this expression basically need to argue

that it is true, right?

And if I can argue that it's true,

then I've proved the upper bound.

In this case, it becomes mini-algebra.

Basically what will happen is we'll drop our absolute value

just because it doesn't really matter

for our practical examples,

and then we'll basically say, oh hey,

I need to find out some value of c,

such that this whole thing is true.

Alright, pick some coefficient.

And I could pick a decent coefficient here.

Usually what you'd just do is pick that coefficient

to be the sum of the coefficients

of everything on the left-hand side.

Maybe you can think about why that would work.

And so I can pick c to be something like five, right,

two plus three, that actually gives me

this expression down here that I've written in the slides,

right, and then this bound, right,

this bound will hold

for some sufficiently large values of n.

And what I can actually do is I can actually solve

that thing for n and basically figure out,

you know, what is gonna be the cut off by which it applies.

So in this case, we're saying

that c is gonna be equal to five,

and this cutoff, this upper bound will apply

for n greater than zero.

So assume that n is integer types,

basically we're saying that one or greater,

this thing will hold.

Okay, so that's a simple example

showing that our bound holds, right?

So we have the basic idea that if I have a growth function,

where I can use that heuristic process

to figure out what the big O is,

and that gives me a suggestion of what it is,

but really in terms of math

we want to show or prove that that is the correct answer,

and the way we do that is by basically showing

that the definition actually holds.

So let's just do one more example.

Over here, what I have my f2,

f2 is log n times 35 n squared.

Once I want to figure out the big O,

well, what I do is I drop all but the dominant term,

in this case I'm dropping the log term,

and then I drop the coefficient on the remaining term.

Remaining term doesn't have a coefficient,

it's really just one behind the scenes,

so I can leave it alone.

So f2 is going to be big O of n squared.

And again, I'm just writing kind of the proper notation

that is also correct.

So f2 is O of n squared.

Okay, so we have that.

On the right-hand side, then,

you have kind of the derivation to show that that's true,

and it's following the same problems

as we did for the last function.

So basically, we look back up at the definition,

f less than g of n, right?

Fill in our blanks, our f of n we know,

our g of n that we're guessing by doing

that elimination of terms,

and then we figure out what is the value of c

by adding in all the coefficients on the left-hand side,

that gives us an expression,

and then we can basically just solve for n, right,

and figure out when is this thing gonna hold.

So it's not too bad for these simple functions.

When you're doing something maybe

with a more complicated function,

then that'll take you a little bit more time,

but the overall process, right, will be the same,

maybe there's just more algebraic steps involved.

Okay, so our big O, right, again,

is this general term that we use

when we're saying that something is an upper bound.

So I have f of n, right, some growth function,

and I'm deriving here my upper bounds for that, right,

which is a big O expression.

Keep in mind the big O is always above another function.

This is good because it gives us kind of our worse case,

where we know our program's gonna take longer

than this amount of time, but on the negatives, right,

big O is basically really easy to write,

because we can just say things like,

oh, something is big O of two to the n, right?

Something that's exponential.

Well, obviously my program is going to be big O of that,

right, that function grows so quickly

that pretty much everything that I could write, right,

in a program will take less time to run than that.

So sometimes people kind of wave their hands,

and just make their upper bounds really big,

but that's not useful for us.

Really what you want to do

is you want to make a big O, right, a upper bound,

that's as close as we possibly can be to the actual f of n.

Right, that gives us kind of more information,

it's closer to it.

Something that's really large, right,

it's just kind of like waving our hands,

and there's just so many functions that are less than it

that doesn't really tell us anything about that f of n.

Alright, so I have one final note here about upper bounds,

and that's about the use of logs.

So it would be true to say the following:

log sub two of n is big O of log sub two of n.

Also, log sub 10 of n is equal to O of log sub two of n.

So I have basically, my left-hand sides are different,

and my right-hand sides are the same,

so I'm saying two different logs resolve to the same big O,

resolve to the same upper bound.

Take a moment to ask yourself,

why might that be the case?

Okay, so the answer there is simply put,

log conversion is a constant time operation, right?

So if I want to switch from log two of n to log 10 of n,

right, if I wanted to do a change of base operation,

I basically just divide by something like, I don't know,

a log of two over base 10 or something,

or log base 10 of two.

All I need to do is that constant time operation,

and that constant time operation,

basically what happens is it gets folded

into the constant within the definition of big O.

So over here I have this c value here.

That c value is allowed to be anything, right,

so that value there basically can soak up the conversion,

right, that little constant that results

from a change of base operation.

So when big O, basically we can be a little bit lazy

and say all logs look the same, right?

Because constant times change those basis,

and that constant time just gets folded into that c

in the definition of the function.

So they're all the same from the point of view

of an upper bound.