[SER222] Recurrences (6/7): Proving f(n)

Summary

El video explica cómo la recurrencia descubierta en la solución de las Torres de Hanoi es equivalente a la fórmula cerrada propuesta (2^n - 1). Se destaca que la recurrencia es menos útil, ya que requiere muchos pasos recursivos para evaluar, mientras que la fórmula cerrada permite calcular directamente el número de movimientos. A través de la inducción matemática, se demuestra que ambas fórmulas coinciden para cualquier tamaño de torre. Además, se realiza un análisis de la complejidad Big-O, que resulta ser exponencial (O(2^n)), lo que implica que el algoritmo es ineficiente para valores grandes de n.

Takeaways

• 📊 El problema trata de comparar una recurrencia con una fórmula cerrada para la solución del problema de las Torres de Hanoi.
• 🔄 La recurrencia no es útil para cálculos rápidos, ya que requiere pasos recursivos hacia atrás, por lo que se busca una fórmula cerrada.
• 🔢 La fórmula cerrada que se sugiere es 2^n - 1, lo que permite calcular directamente el número de movimientos necesarios para cualquier n.
• 🧮 La recurrencia tiene dos partes: f(1) = 1 (un solo disco requiere un solo movimiento) y f(n) = 2 * f(n-1) - 1 para n discos.
• 🔍 El objetivo es demostrar mediante inducción que la fórmula cerrada y la recurrencia coinciden para cualquier valor de n.
• 📐 La inducción tiene dos pasos: primero, mostrar que la base (f(1)) es verdadera, y luego mostrar que si se cumple para k, se cumple para k+1.
• 🧩 Se asume que la fórmula es verdadera para k, y luego se demuestra que también es válida para k+1 utilizando la recurrencia.
• 📈 Al final, se demuestra que la fórmula cerrada es válida para todos los números naturales mediante inducción.
• 💡 La fórmula final para f(k+1) es 2^(k+1) - 1, lo que coincide con la fórmula general que se quería demostrar.
• ⚙️ El crecimiento de la función es exponencial (O(2^n)), lo que implica que el algoritmo toma mucho tiempo para valores grandes de n.

Q & A

¿Qué es lo que se quiere demostrar en el video?

Se quiere demostrar que la recurrencia obtenida del problema de las Torres de Hanoi es equivalente a la fórmula cerrada que se conjeturó para el número de movimientos.

¿Por qué no es útil la recurrencia para evaluar el número de movimientos?

Porque para evaluar la recurrencia en un valor específico de n, se requieren muchos pasos recursivos, lo que la hace ineficiente. Es más útil tener una solución cerrada que permita calcular directamente el número de movimientos para un valor de n.

¿Cuál es la recurrencia y la fórmula cerrada propuestas para el problema de las Torres de Hanoi?

La recurrencia es f(n) = 2f(n-1) - 1, y la fórmula cerrada conjeturada es f(n) = 2^n - 1.

¿Cómo se puede demostrar que ambas fórmulas son equivalentes?

Se puede demostrar utilizando inducción matemática. El objetivo es probar que ambas fórmulas son iguales para cualquier valor de n.

¿Cuáles son los pasos clave de la inducción matemática mencionados en el video?

Primero se debe establecer un caso base, en este caso n = 1, y luego realizar un paso inductivo, que demuestra que si la propiedad es cierta para un valor k, entonces también lo será para k + 1.

¿Cuál es el caso base utilizado en la demostración?

El caso base es n = 1, donde se demuestra que ambas fórmulas, f(1) = 1 y 2^1 - 1 = 1, son iguales.

¿Cómo se realiza el paso inductivo?

En el paso inductivo se asume que la fórmula es válida para n = k y se utiliza la recurrencia para demostrar que también es válida para n = k + 1.

¿Cómo se expande algebraicamente la fórmula durante el paso inductivo?

Se sustituye la expresión f(k) en la recurrencia y se simplifica para obtener que f(k + 1) = 2^(k + 1) - 1, mostrando que la fórmula es válida para k + 1.

¿Qué significa que la solución sea de tiempo exponencial?

Significa que el número de movimientos necesarios crece exponencialmente con el número de discos. Esto implica que el tiempo de cálculo aumenta rápidamente, haciéndolo impracticable para valores grandes de n.

¿Cuál es el orden de complejidad Big-Oh de la solución?

El orden de complejidad Big-Oh es O(2^n), indicando que el número de movimientos crece de manera exponencial con el número de discos.

Outlines

00:00

🔍 Introducción y análisis del problema de Torres de Hanoi

El autor presenta el problema de las Torres de Hanoi y menciona que el objetivo es mostrar que la recurrencia obtenida es equivalente a la solución en forma cerrada. Explica que la recurrencia no es práctica para evaluar el número de movimientos requeridos para un tamaño específico de n, y por lo tanto es mejor una solución cerrada. Se detalla la recurrencia de f(1) = 1 para un disco y la de f(n) = 2f(n-1) - 1 para n discos. Finalmente, se plantea que la solución cerrada propuesta es 2^n - 1, y el objetivo es probar que ambas fórmulas son equivalentes para cualquier n usando inducción.

05:00

🔄 Comparación entre fórmulas mediante inducción

Se introduce la idea de la inducción matemática como herramienta para probar que las dos fórmulas (la recurrente y la cerrada) son equivalentes para todos los tamaños de torres. Se explica el proceso de inducción, comenzando con un caso base (n = 1) donde ambas fórmulas son iguales. El propósito de la inducción es demostrar que si la propiedad es cierta para un valor k, entonces también lo será para k+1, lo que permite cubrir todos los números naturales. En el caso base, se sustituye n = 1 en ambas fórmulas y se concluye que son iguales, estableciendo que la propiedad es cierta para n = 1.

10:03

📏 El paso inductivo y su importancia

El autor explica el paso inductivo, donde se asume que la propiedad es cierta para un valor k y se debe demostrar que también es válida para k+1. Se muestra cómo esta suposición inductiva ayuda a construir la solución para el caso siguiente. Utilizando la recurrencia original y la suposición inductiva, se deriva la fórmula para f(k+1). El objetivo es llegar a la forma cerrada f(k+1) = 2^(k+1) - 1, lo que demostraría que la propiedad se mantiene al avanzar un paso en la secuencia.

15:04

🔑 Resolviendo algebraicamente la relación de recurrencia

En este párrafo, se realiza un desarrollo algebraico para demostrar que la fórmula para f(k+1) es equivalente a 2^(k+1) - 1. Se parte de la fórmula original y se utiliza la suposición inductiva para avanzar de k a k+1. Se destaca que el resultado debe coincidir exactamente con la forma cerrada deseada. Tras expandir y simplificar las expresiones, se llega a la fórmula correcta para f(k+1), demostrando así que la suposición inductiva es válida y que ambas fórmulas son equivalentes para todos los valores de k.

📊 Conclusión sobre la equivalencia de las fórmulas

El autor concluye que, dado que se ha demostrado que las fórmulas coinciden para el caso base y para el paso inductivo, esto implica que las dos fórmulas son equivalentes para cualquier valor de n. Así, se ha probado que la solución cerrada 2^n - 1 es correcta. También reflexiona sobre las implicaciones de tener una solución cerrada, destacando que es mucho más eficiente que una recurrencia para calcular el número de movimientos requeridos.

📉 Análisis de la complejidad temporal de la solución

Finalmente, el autor analiza la complejidad temporal de la solución cerrada. La función de crecimiento f(n) = 2^n - 1 se clasifica como una función de tiempo exponencial con una complejidad de O(2^n), lo que significa que el tiempo requerido para resolver el problema crece muy rápidamente a medida que aumenta n. Se menciona que esto es problemático para valores grandes de n, ya que el tiempo de cómputo sería ineficiente. También se calcula el valor tilde de la función, que es igualmente 2^n, destacando que esta es una función de crecimiento considerable.

Keywords

💡Recurrencia

Una recurrencia es una ecuación que define una secuencia de valores en términos de valores anteriores de esa secuencia. En el video, la recurrencia es usada para describir cómo calcular el número de movimientos necesarios para resolver el problema de las Torres de Hanói de forma recursiva, es decir, calculando el número de movimientos para una torre de tamaño n en función de n-1.

💡Solución cerrada

Una solución cerrada es una fórmula matemática que permite calcular el resultado de un problema sin necesidad de recurrencia o pasos iterativos. En el video, el objetivo es encontrar la fórmula cerrada que permita calcular directamente el número de movimientos necesarios para cualquier número de discos en las Torres de Hanói, lo cual resulta en la fórmula 2^n - 1.

💡Inducción matemática

La inducción matemática es un método de prueba que demuestra que una afirmación es verdadera para todos los números naturales. En el video, se usa inducción para probar que la fórmula cerrada (2^n - 1) es correcta para todos los tamaños de torres, comenzando por un caso base y luego demostrando que si es verdadera para un valor k, también lo es para k+1.

💡Caso base

El caso base es el punto inicial de una prueba por inducción, donde se verifica que una afirmación es verdadera para el valor más pequeño posible. En el video, el caso base se establece cuando n es igual a 1, mostrando que tanto la fórmula recursiva como la solución cerrada coinciden para una torre con un solo disco.

💡Paso inductivo

El paso inductivo es el segundo componente de una prueba por inducción, que demuestra que si una afirmación es verdadera para un valor k, también lo es para k+1. En el video, se utiliza el paso inductivo para demostrar que si la fórmula cerrada es válida para un número de discos k, también será válida para k+1, consolidando así la validez de la fórmula para cualquier n.

💡Torres de Hanói

Las Torres de Hanói son un problema matemático donde se deben mover discos de diferentes tamaños entre tres postes siguiendo ciertas reglas. En el video, se utiliza este problema para ilustrar la recurrencia y la fórmula cerrada que calcula el número mínimo de movimientos necesarios para resolver el problema dependiendo del número de discos.

💡O grande (Big-O)

El O grande es una notación utilizada para describir la complejidad algorítmica en términos de crecimiento respecto al tamaño de la entrada. En el video, se menciona que la complejidad del algoritmo de las Torres de Hanói es O(2^n), lo que indica un crecimiento exponencial en el número de movimientos necesarios a medida que aumenta el número de discos.

💡Algoritmo exponencial

Un algoritmo exponencial es aquel cuya cantidad de pasos necesarios para completarse crece de forma exponencial con el tamaño de la entrada. En el video, se explica que el problema de las Torres de Hanói tiene una complejidad exponencial, lo que implica que el número de movimientos necesarios se duplica con cada disco adicional, haciéndolo ineficiente para valores grandes de n.

💡Función de crecimiento

Una función de crecimiento describe cómo varía el número de operaciones de un algoritmo en función del tamaño de su entrada. En el video, la función de crecimiento de las Torres de Hanói es 2^n - 1, lo que significa que el número de movimientos crece exponencialmente con el número de discos.

💡Hipótesis inductiva

La hipótesis inductiva es el supuesto en una prueba por inducción de que la afirmación es verdadera para algún valor k. En el video, esta hipótesis se utiliza como parte del paso inductivo para asumir que la fórmula cerrada es válida para k discos y luego demostrar que también lo es para k+1 discos.

Highlights

The recurrence for the Towers of Hanoi solution is expressed as f(n) = 2f(n-1) - 1.

A closed-form solution is preferred over the recurrence because it allows for direct computation of the number of moves.

The closed-form solution for the Towers of Hanoi problem is f(n) = 2^n - 1.

Induction is used to prove that the recurrence formula and the closed-form solution are equivalent for all values of n.

The base case for induction starts with n = 1, where f(1) = 1, and the formulas are verified to be equal.

The inductive step assumes the property holds for some k and proves it holds for k + 1.

The recurrence relation f(n) = 2f(n-1) - 1 is used to transition from f(k) to f(k+1) in the inductive step.

Algebraic manipulation shows that the closed-form solution holds after expanding and simplifying the recurrence.

The final form of the solution is f(k+1) = 2^(k+1) - 1, proving the inductive step is valid.

The overall proof shows that the recurrence and the closed-form solution are equivalent for all natural numbers n.

The algorithm for solving the Towers of Hanoi problem has a time complexity of O(2^n), indicating exponential growth.

The exponential time complexity means the problem becomes computationally infeasible for large values of n.

The tilde notation for the growth rate is also 2^n, providing a more precise representation.

Exponential growth is highlighted as a key challenge in the Towers of Hanoi problem, making it hard to solve for large inputs.

The analysis concludes with a detailed understanding of the algorithm's behavior and performance limitations.

Transcripts

- So in this video, I wanna show that our recurrence

that we basically had come up with

from looking at the solution to Towers of Hanoi

is actually the same thing as our guess

for what is the closed form version of it.

Again, right, the recurrence isn't very useful to us,

because basically whenever you wanna evaluate

for specific n,

we have to basically do all these kinda recursive steps

where you go backwards, backwards, backwards, backwards,

really what's more useful

is for us to have a closed solution

that we can basically put in our value of n

and directly compute

what is the number of moves that are required.

So stuff we've basically discovered already

is this stuff over here.

So this is basically our known truth.

This little bubble over here with "Ahem" over there

as kind of a side note,

we're kind of just taking this to be true, right?

If there was an issue in the way we analyze our code,

maybe this won't be true,

but we're just going to basically assume

that our initial analysis

or our initial occurrence is accurate.

So there's two parts to the recurrence.

First of all f of one equal one.

So basically for the very small tower

containing just one disc,

if I wanna move it,

well that takes just one move, so pretty simple.

Second thing there was more complicated is the f of n,

the general step.

So f of n equal two f of n minus one minus one.

So this is the recursive part where the number of moves

required to move a tower of size n

is based on the number of moves required

to move two smaller towers,

two size n minus one towers.

Okay, so that's what we have

and then based on our guesses that we made before,

we think that the closed loop solution

looks something like this,

two to the n minus one.

And so our goal basically is to show

that for any n, right, any size tower,

these two things will always be the same.

An issue, right, we know that these are the same

in terms of just what we plotted out.

So if you think back,

we had basically this graph,

we started at zero,

we went up to something like 16

and we just evaluated these two functions

for each of those values of n

and they looked the same,

but the problem is how do I make sure

that they're always the same, right?

Forever that they will match up.

Well, we can do that using induction, right?

So the idea of induction again, right,

is to show that some property holds true

for every value of n, right.

Basically, we're asserting that something is true

for every element of a set.

Here, the set that we're looking at

is the set of natural numbers.

Well, we're starting at zero basically

and going up by one

and we wanna show basically,

for any possible tower, right,

that's maybe our set, is tower sizes,

that this property holds,

that these two things match up.

That's what we wanna assert

and we wanna assert it

that for basically any size of tower,

these things will hold,

not just the size of towers

that we have listed in our table,

we wanna assert it for everything.

Okay, so how do we get there?

Well, first thing we gotta do

and induction generally has two parts,

first of all we need to decide what n is bound to

and so we're bounding n to starting at one

and going upwards

and then, well, we could also started at zero,

but it doesn't really make sense to move an empty tower,

so we'll start at one, so we'll use natural numbers.

Well, we need to basically decide what variable

we're iterating over, if you would.

What is the set that we're going to prove things from?

So, that here is just natural numbers.

I'll make a note that this variable, n,

basically the size of towers is coming from that set,

it's a natural number.

Now, for induction, there are basically two parts.

First of all, we need to start with the inductive case,

which is basically like what is the simplest thing

I can show to be true, right, a starting place

and then if I have that,

then what I wanna do is go look at the inductive step,

which is going to say, okay,

given that a particular,

that this property holds for k, right,

for some tower size,

that it'll also hold for some larger tower, right?

Tower size plus one, k plus one.

That's the inductive step.

That lets us basically grow

and eventually touch each of the natural numbers, right,

because if my property can be shown true

for some number like 10,

then that will let me show it true for 11

and if it's true for 11,

then it's also true for 10 by using that same rule.

So that rule, right, that inductive step,

basically lets us span all the natural numbers

and assert that our property holds for everything.

This is rather nice

because if you think about it,

well, natural numbers,

there's a countably infinite number of them, right?

And we're gonna basically show

that this property holds for all them,

even though we're just doing it in this one case,

it'll work for all of them.

All right, so looking at our two steps,

first thing we need to talk about is the base case.

So in terms of the base case,

basically what I wanna do

is I wanna show that

what I'm trying to prove

basically holds true at some starting place

and the starting place I'll go with

is actually n equal one.

All right, and so n equal one be my base case

and what I would do is basically put that value for n

into my formulas.

So I know of course, right, that f of one equal one,

so over here basically I can write this stuff here,

f of one equal one

and then I'm trying to assert, right,

that that'll be equal to the other formula,

the formula that I guessed,

so that's this formula here.

So this basically comes down over here

and I've basically just set n equal to one.

So there's two parts here, right,

so this stuff over here comes from this.

This stuff over here comes from the one above

and if I evaluate those, right,

I'll find out that I get one and one, right?

This is obviously true,

so at least for that base case of n equal one,

the property holds, right?

Those two things are the same.

So when I say property,

I really mean here those two formulas are equal.

Right, we could be asserting many facts, right,

we could be asserting something like,

oh, the number of discs in the tower is odd or even

or something like that,

but the property we want to investigate

is just to check to see whether those two things are equal,

whether my guessed formula

and my formula that I came up with based on the code

give me the same result.

So for here, right now,

I've basically shown that to be true.

Okay, so let's now take a look at the inductive step.

So the inductive step,

basically my job is to say, okay,

this property holds for some k

and that will imply that it holds for some k plus one,

and that property being of course

that those two things are equal.

So here I get a little bit of somehow, of magic,

so I'm actually allowed to assume

that case k is true.

So this little bit here.

So this is basically coming from our guess, right,

our guess was over here up top

for our original f of n.

Now, we're saying is that inductively,

well, in terms of induction,

what we'll assume, basically,

is that this holds, right,

so we're going to be given that case k holds, right?

So we're given this as true.

Even though we haven't really done anything,

we're just going to assume it.

That's something there that's basically available

for us to use algebraically.

Okay, and really the only difference, right,

is I've substituted in k for n

to basically represent

that this is kind of your inductive hypothesis, right?

This is what you're allowed to assume.

So, using that kind of fact, right,

we wanna build from that,

we wanna show that this is valid as well.

Basically we want a way to derive f of k plus one

from f of k, right?

We wanna link those two things up, right?

Get the ability to basically step forward

and say if this is true,

this other thing is true as well.

So how can we get there?

And actually, maybe before I get there,

what is our end goal?

Our end goal is really something like this.

We wanna recover the following formula.

We wanna recover f of k plus one

equals two k plus one minus one, right?

That's what we wanna recover.

So we wanna get from this initial f of k

to f of k plus one, right?

We wanna move between those algebraically,

not kinda make any assumptions

and just using the information that we have.

So that's kind of our goal.

So we start with f of k,

so what can we do?

First thing we can do is actually think about

using our, basically our original formula,

the recursive one, the recurrence

to write an expression

that basically computes f of k plus one, right?

Because our initial recurrence stuff up top, right,

those two ways to compute f of one, f of n,

notice the recurrence,

those are gonna be valid no matter what.

We already took that to be true.

That is our stuff we get basically forever, right?

It's free for us to use.

So what I could do is I could think about writing

the expression for f of k in terms of that original rule.

And so that's basically what we've done here.

We have basically a few things going on.

I'm shifting a little bit, right?

The original rule is written in terms of f of n,

now we're basically saying n equals k plus one,

so we're doing a substitution in a couple of places here

and we end up with this thing here.

So this is basically my formula for f of k plus one

in terms of that original formula

and then what I have, right,

is I have that reoccurrence going on

and that recurrence is normally referring back

to a smaller value of the function, right?

So here it's referring back to f of k, right?

So f of k plus one is computed from f of k.

But here, right, this isn't really what I want, right?

Again, think of my goal, right?

My goal is to get to this thing over here,

where my expression, that's a closed form expression

that doesn't have any functions being called

or referred to.

So actually, I'm not bound

to the line that I'm manipulating,

this f of k, what I can actually do

is I can actually substitute in this over here, right,

so I'm substituting in what I assume to be true.

So that brings me, basically, to this line right over here.

So in a sense, what's happened between these two lines

is I said, okay, I wanna get from k to k plus one.

I'll actually start with the thing

that I'm allowed to assume, right,

that my formula or my property holds for f of k

and then I'm somehow gonna grow it, right?

I'm gonna move it forward using my original formula,

because for sure that original formula will work, right?

And the whole purpose of that formula, right,

the actual line up here,

this thing, right, really, mechanically,

what it's doing is it's evaluating some value

for a tower based on a smaller tower,

so it's linking together, right,

a tower of size n with a tower of size n minus one

and so what I'm doing over here, right,

is I'm trying to at the bottom

prove that the case k implies the case k plus one

and so that original function I have,

basically that's the mechanic I have to do that, right?

To jump from k to k plus one

because I don't have anything else

that can get me between those two points,

so I start with what I assume, right,

I assume that that property, that expression, right,

holds for f of k

and I use my original known good formula to move up by one.

So we're kind of combining two things here.

We're combining our assumption

with basically the way we stepped forward

in the original recurrence.

So that gives me this line down here

and this line down here,

all of a sudden I've eliminated f of n,

and so I have this f of k plus one

being equal to two of the k minus one plus one,

so I have that.

The problem is I'm not really done yet.

So that's kind of a full expression there,

but it doesn't look just like that, right?

This thing over, right, our goal.

Really, what we want, is you want that exactly.

And the reason why we want that exactly

is because this over here, this stuff,

looks exactly like what we're allowed to assume,

that f of k equal to k plus two to the, excuse me,

f of k equal to the k minus one, right?

These two things look exactly the same,

this f of k and this f of k plus one.

The only difference, right,

is that there's a plus one basically, where the k is, right?

So whatever it is, the expression that we produced

should look exactly the same

except for that plus one being added on to there, right?

If there's still other kind of things

to algebraically manipulate, we gotta take care of 'em.

We can't just leave this be

and say, oh hey, I wrote f of k plus one

with stuff that's not a recurrence, right?

There's no f of n on the right hand side,

I can't stop there.

Algebraically, I need to carry through

and make sure that I match my goal, right?

My goal is to basically regenerate this f of k,

but with the plus one added to that k.

Okay, so from this point, it's just algebra.

So I have here, right,

my two times two to the k minus one plus one

so I expand basically the coefficient,

so I multiply it in.

That gets me basically two to the k plus one minus two,

right, so just imagine you're distributing, right, in there,

so your minus one is times two, gets you minus two

and then you're doing basically two times two to the k,

well, what happens is that power, right,

because the coefficient matches what your power's on,

the power will absorb the coefficient out front,

so we now have a two to the k plus one.

Almost done there, right,

then we just basically do the addition,

add that one to the negative two

and we over here, two to the k plus one minus one.

So in this case, right,

here we've basically managed to carry through

and we've recreated the original formula

that I started with,

but with basically that plus one now in there.

So that's it, we're done, right?

Idea there, right, is basically where we're recovering

that f of k, right?

We wanna show that starting with the assumption

that f of k is valid, right,

that that expression holds,

then we can show the case k plus one will hold

and we would do that basically

by recovering the original formula,

but with that slight alteration of that plus one.

And the way we got there, right,

the way we got there from f of k to f of k plus one

is basically by using my original formula,

my original recurrence

to do that little step forward, right,

to basically do the work

of making a prediction, right, for a tower that's one bigger

and that's a legit step for us, right,

because we know that recurrence is our assumed truth, right,

and so we can use that to basically take a step, right,

and say okay, the k plus one step is also true.

So putting this together, basically, what we have, right,

is we have our base case and our inductive case, excuse me.

We have our base case and our inductive step,

so base case says hey, these two formulas match up

for k equals zero, great.

Then we have our inductive step which says okay,

if those formulas hold, right,

if the property holds for k,

then it'll hold for k plus one.

Well, there you go, done, right?

So we start at zero, plus one it, get to one,

plus one that, get to two,

plus one that, get to three,

plus one get to four

and so on, right?

So putting this together,

basically every single value of n, right,

all the natural numbers,

these two things will be the same, right?

We proved that,

and so now we know that our two formulas, right,

our guess and the reoccurrence we got from the code

are the same thing, right?

So that is accurate guess, right?

We've proved that they're the same,

so now we're good to go.

Some final remarks here about the f of n.

So basically what we've done, right,

is we've verified that we have a closed solution.

We had a solution before,

but the problem was it was recursive, right?

It was a recurrence,

so it was expressed in terms of itself.

It's very hard to evaluate,

but now we have what we want,

which is a closed form

or a closed loop solution to it.

Given that we have f of n, right,

which is a growth function, right,

it's gonna exactly compute for us

the number of moves we require,

we can actually now think about maybe computing

the Big-Oh or even the tilde of it,

or whatever we want of it.

So maybe think for a second.

Given this function here,

this f of n equal two to the n minus one,

what would be the Big-Oh order of that

and then what will be the tilde of that?

So maybe think for one second.

Okay, so Big-Oh for that is going to be,

it'll be Big-Oh of two to the n,

which is actually something

that we haven't really seen before.

Before, we've seen things like O of n or O of n squared,

but here this is O of two to the n,

so this an exponential time algorithm.

The problem with exponential time algorithm

is it's that'll basically take forever, right?

So as I increase n, right, the number of discs,

this will grow very, very, very, very quickly, right?

It'll grow exponentially quicker

just going from 10 to 11 for our size of n

all of a sudden doubles the number of moves

that are required.

And this is very bad, right?

This is something basically

for any reasonably large number of n,

we're just not gonna be able to compute.

It'll simply take too long.

Then what about tilde?

Tilde for this is going to be also two to the n.

So remember the difference between Big-Oh and tilde

was that Big-Oh doesn't drop the coefficient in front.

Instead we just leave it there

in order to be more accurate.

Okay, so that's kind of our growth function right up top.

Those are our Big-Oh and tilde analysis of it.

So pretty good, we now have this idea

of how this algorithm will work.