0:00

In the previous video, we proved that the running time of the Warshall

Â algorithm on a sequence consisting of n elements is big log of n.

Â In this video we will show that this bond is essentially optimal.

Â We will do this by showing that any correct sorting algorithm

Â that sorts an object by comparing pairs of them.

Â Must make a clear stand log in operation such as particularly in the worst case.

Â Once again we say that the sorting algorithm is comparison based

Â if it sorts the given objects just by comparing pairs of them.

Â We can imagine the following situation, we have add objects, that look the same, for

Â example in walls, but have different weights.

Â And we also have pen balance.

Â And this pen balance is, our only way to compare pairs of these balls.

Â And our goal is to rearrange these balls, in order of increasing weights.

Â 1:00

So, for example, the two source and algorithms that we'll already consider it,

Â namely the selection sort algorithm and the merge sort algorithm are both

Â comparison based algorithms.

Â So for example, the selection sort algorithm at each region

Â finds the minimum value in the remaining part of the array.

Â And it does so exactly by comparing pairs of objects, right?

Â Also, the merge sort algorithm is also comparison based algorithm.

Â So it first splits an array into halves.

Â And then it needs to merge the two results in arrays.

Â And when merging the results in arrays, it also uses comparisons, right?

Â So we take the first two elements of two sorted arrays.

Â We compare them, and based on this comparison we take one of these elements

Â out of one of those two arrays and put it to the result in the array.

Â So this as a formal statement that we're going to prove.

Â It says that any comparison based algorithm

Â that sorts an object has running time.

Â At least big and n log n in the worst case.

Â So but in otherwise we can say the following.

Â Assume that you have an algorithm that sorts an object

Â by comparing pairs of them.

Â It can be the case that for some given both sequences of an object,

Â your algorithm performs less than analog operations.

Â Say, linear number of operations.

Â However, it cannot be the case that your algorithm always sorts in time,

Â asymptotically less than n log n.

Â Meaning that, there must exist, sequence of objects, on which your algorithm

Â 2:50

will perform at least performing a login comparison to sort such sequences.

Â Any comparison based algorithm can be shown as a huge tree that contains all

Â possible sequences of comparisons that can be made by this algorithm.

Â For example, here on the slide.

Â We show a simple algorithm that sort three object.

Â Three objects.

Â So it starts by comparing a1 and a2.

Â If a1 happens to be smaller than a2,

Â then we proceed to comparing a2 and a3.

Â If a2 is smaller than a3, then we already know the permutation

Â of the input three objects in non-decreasing order.

Â Namely, we know that a1 is smaller than a2,

Â and we know that a2 is smaller than a3.

Â So we can just output the following permutation.

Â 3:49

Right.

Â If on the other hand, a2 happened to be at least a3,

Â then at this point we already know that a2 is greater than a1.

Â And a2 Is no smaller than a3.

Â So at this point, we know that a2 is the maximum element among our three elements.

Â However, we still need to compare a1 and a3, so we do this comparison,

Â and based on its result, we output either this permutation or this permutation.

Â 4:32

So we proceed similarly in this case.

Â So this is just a toy example for an algorithm for

Â a comparison based algorithm comparing three objects, sorting three objects.

Â However, such a huge tree can be drawn for any comparison based health algorithm.

Â So at the root of this tree we have the first comparison.

Â And its children will label just the next

Â comparison that is made based on the result of the first comparison and so on.

Â So each internal node is labeled with some comparison.

Â And each leaf is labeled with a permutation of m input objects.

Â 5:12

A simple but crucial for this argument observation is that in this tree,

Â we must have at least n factorial leaves.

Â And this is because we have n factorial different permutations of n input objects.

Â Where n factorial is defined to be the product of n and minus one and

Â minus two and so on.

Â So why is that?

Â Why we must have any possible permutation as a leaf in our tree?

Â Well, this is just because it is possible that this permutation is a lead output,

Â is the right output of our algorithm.

Â So for example on our previous slide, on our toy example, we have three objects and

Â there are six possible permutations of these three objects, and

Â there are six leaves in our tree.

Â For example one of them is 213 and it says that the second element

Â is the smallest one, then goes the first element, and then goes the third element.

Â And indeed there are cases when this is the right answer.

Â Right?

Â So when the input data consists of three objects,

Â such that the second element is the smallest one,

Â the first one is the next one, and the third element is the largest one.

Â Right?

Â So once again, you have a huge tree which carries a comparison based algorithm.

Â There must be at least n factorial leaves,

Â because each possible permutation must be present as a leaf in our tree.

Â 6:44

So on the other hand the maximal number of

Â comparisons made by our algorithm corresponds to the depths of our tree.

Â So the depths is defined as the maximal number of edges run away

Â from the root to the leaf, to some leaf of our tree.

Â So and this is exactly the maximal possible number of comparisons

Â which our algorithm makes.

Â So now we would like to show that d must be large in our case,

Â must be at least be big O omega of analog n.

Â And we know already that our tree contains many, many leaves.

Â Mean n factorial is a function that grows extremely fast.

Â Okay so, intuitively we would like to show that if a tree has many,

Â many leaves, then it has a large depth.

Â And at least intuitively this clear.

Â If you have a tree of very small depths then it must just a few leaves, right?

Â But, we know that it has many, many,

Â many leaves, in fact at least ten factorial leaves.

Â To formally show this we need the following, we need the following estimate.

Â The depths of a binary tree is at least a binary algorithm of its number

Â of leaves or equivalently 2 to the depths is at least its number of leaves.

Â Well this can be proved formally, but let me just show you this informally.

Â Let's concede a tree for example of depth 1.

Â So in this case, d is equal to 1.

Â And it is clear that the maximal possible number of leaves

Â in a tree of depth 1 is equal to 2.

Â So now, let's try to understand what is the maximal possible

Â number of leaves in a depth of In a tree of depth 2.

Â For example, this is a tree of depth 2.

Â This is another tree of depth 2, it has has three leaves.

Â And this is a tree of depth 2 that has maximal possible number of leaves,

Â in this case it is 4.

Â It is 2 to the d indeed.

Â And intuitively it is clear that to have a tree of depth d that has

Â maximal possible number of leaves.

Â We need to take a tree which has a full binary tree of depth d, right?

Â And this tree has exactly 2 to the d leaves.

Â So the maximal number of leaves in a tree of depth d is 2 to the d.

Â 9:34

It remains to estimate log of n factorial.

Â We're going to show here that log of n factorial is at least c times n log n.

Â Which means as it works that log of n factorial is big log of n log n.

Â To do this, we express n factorial as a product of 1, 2, 3.

Â And so on n minus 1, and

Â then right algorithm of product of these numbers as a sum of their algorithm.

Â So, log of n factorial is equal to log of 1 plus log of 2 plus log of 3 and

Â so on plus log of n.

Â So, this is a sum of an object.

Â Let's just throw away the first half of this and elements,

Â and leave only the second half.

Â So in this second half, we have n over two elements and

Â each of them is at least log of n over two, right?

Â So this has algorithms of numbers which are at least n over two.

Â So we have n over two.

Â Elements, each of them is at least algorithms of n over 2.

Â This allows us to conclude that log sum is at least 10 over 2 times log of n over 2.

Â And this in turn be big log of n for a simple reason.

Â So log n over 2 is equal to log n minus 1.

Â Well, this grows like log n, right?

Â Because log n is a growing function and one is a constant so

Â again minus one goes as log n.

Â And over grows as n, right?

Â So, this is up to constant factors, this is just n.

Â So, n over two times log n over two grows like n log n.

Â 11:16

Okay so this concludes our proof, and

Â this concludes the proof of the fact that any comparison based

Â algorithm must make at least n log n adorations in the worst case.

Â Once again, another conclusion is that when merged sort algorithms that we

Â considered in the previous lecture e is asymmetrically optimal.

Â In the next video we will see an algorithm that actually sorts

Â n given objects in time less than n log n.

Â Actually in time just in linear time.

Â In time big log of n however,

Â it will sort the n given objects, knowing something about these objects.

Â It will only sort the given objects if the subject has small integers.

Â And we will sort them without actually comparing them to each other.

Â