Hello.
In this video, we will talk about algorithms belonging to the exponential complexity class.
In order for us to understand how quickly an exponential curve grows.
I am going to make use of an old fable.
There was once a king that grew bored of his daily routine, and he wanted a new game that he could
play with his friends.
An inventor came along and came up with the game of chess.
This is the chess as we know it today, the one with an eight by eight chess board.
Apparently, the king was so happy with this game and he was having so much fun.
He understood the rules very quickly and he wanted to reward the inventor of the chess game with something.
So he asked him for anything that he wanted.
He could choose anything that he want, and the king will make sure to give it to him.
This inventor asked for a very simple thing.
He wanted Rice to feed his family.
He asked for the king to give him the equivalent of rice.
If one had to put a single grain of rice on the first square of the chessboard.
Then you double it and you put two grains of rice on the second one, and then you put four on the third
one and so on.
So on the fourth box you would put eight grains of rice.
After that, you would put 16 grains of rice on the fifth box.
Then 30 to 60 412825, six, five, one, two, and so on.
Until you filled the entire chessboard, always doubling the amount of rice per box that you have on
the chessboard.
The king was really happy because he thought he got this amazing game for just a few grains of rice
and he promised this inventor to get his rice.
Unfortunately, what the king didn't know is that by the time you get to the 64th box of our chessboard,
you get into an astronomical number, an absolutely huge number.
The amount of rice that the king would have to give him just on this last square is equivalent to around
368 billion tons of rice.
To put this in context, the entire world consumes around half a billion of tons of rice every year.
The fable finishes by the king getting really angry and eventually ordering the inventor of chess to
death.
So it didn't really work out very well for the inventor of chess.
But this is a simple story just to explain how quickly exponential curves.
Kangaroo.
If you don't believe me, you can try to work this out yourself.
You can try to keep on multiplying the number of rice by two on each square until you get to the 64th
square and you'll see you'll get to that number.
There is a quicker way to work out the exponential value at a particular point in time.
If the King knew about this, he wouldn't have fallen into this trap.
And this is by using simple maths.
We can start by one and multiply it on each time.
So one, two, four, eight, 16, and so on.
And we do it 64 times until we get to that huge number.
Or we can simply use powers.
We number each box in our chessboard from zero up to 63.
Remember that?
64 boxes, if we start from zero, we have 63 on the final box.
And to work out how many grains of rice we need to put on each box, we can go directly.
We don't need to work one after the other.
Let's try to reason how to come up with this simple expression.
Remember, we start from one and then we multiply that by two, so one times two.
Then we have the previous result, which is two times two again, and then we have the previous result,
which is four and four is also two times two.
So we have two times, two times two and to get to 16 we have the eighth.
The previous result, which is two times, two times two, and we multiply it by another two.
And for all of this we can use the expression two to the power of and to give us the result.
So to give us the position at box number zero, we do two to the power of zero, which gives us one
two to borrow, one gives us two to get the value on position two, we do two to the power of two,
which is essentially saying two times two and giving us four.
Then we have two to the power of three, giving us eight, which is two times, two times two.
And then we have two to the power of four giving us 16 and so on.
We can find the value of any box on the chessboard.
And if we have to work out the final number, we do two to the power of 63 and gives us this huge number.
In this section we will describe algorithms that have a runtime or a spacetime complexity of order C
to the end and is the input size of our algorithm and C is a constant.
In the previous example of the chessboard, C was two and was the number of the box that we wanted to
find.
How many rice we had on that box, we can't compare.
This exponential class with other classes in this graph, you see the comparison with quadratic, which
is this one over here and linear, which is this green one over here.
You can see that the exponential growth grows much faster than the quadratic one.
This chart is very typical when you are comparing the different complexity classes and in fact you can
find many similar charts online if you just Google it.
However, it's not showing the complete picture.
You might be fooled into thinking that the exponential class is slightly worse than the quadratic one.
This is wrong.
The exponential curve grows much faster than the quadratic one.
If you notice in this chart the X-axis, the size of our inputs, this chart stops at around and equals
five.
If we zoom out and increase the input size just to slightly over ten, you can see how much faster the
exponential curve grows compared to both the linear and the quadratic.
Even with an input size of size 20, the problem typically has already become too huge for your computer
to handle, either in terms of memory or in terms of runtime.
And in this chart, you can also see that even when the input size is just around 20, there is no comparison
with the exponential and the quadratic.
The quadratic curve on this chart looks like a straight line because it's being squashed by the exponential
curve.
In the next video we will discuss and implement an algorithm that belongs in this complexity class.
The Exponential Complexity class.