0:02

with mergesort is a good opportunity to take a look at the intrinsic difficulty in

Â the sorting problem, now that is called complexiting and we'll look at that next.

Â The idea of complexity is it's a frame work for studying the efficiency of all

Â the algorithms for solving a particular problem. That's called Computational

Â Complexity. And in order to do this sensibly, we need what's called a model of

Â computation. The operations that the algorithms are allowed to perform. For

Â sorting that's kind of straight forward, what we're going to do is have a cost

Â model where we count the comparisons. Now in framing of the difficulty of problems

Â were only two things. One is an, what's called an upper bound which is a cost

Â guarantee that's provided by some algorithm for solving the problem. That's

Â an upper bound and how difficult it is to solve the problem. We have an algorithm

Â that can solve it it's the least that easy. And then we also look for a lower

Â bound which is a limit on the cost guarantee of all algorithms. No algorithm

Â can do better. Now, what we seek ideally is what's called an optimal algorithm

Â where we prove that the upper bound and the lower bound are the same. That's an

Â algorithm that's, that we know that has the best possible cost guarantee. That's

Â the idea for solving any problem. So, for sorting, let's look at what each of these

Â are. The model of computation is what's called a decision tree, tree. And what

Â that mans is that all we can use is compare, that's the only way we can access

Â the data. So, our cost model is the number compares. Mergesort provides, provides an

Â upper bound, that's an algorithm that's guaranteed to get the sort done in time

Â proportional to N log N. And what we'll look at now is the lower bound. There's a

Â trivial lower bound which says you have to look at all the data, that's N and we'll

Â look at a better lower bound and see that mergesort is optimal. So, here's the basic

Â idea for proving a lower bound for sorting. Let's say, we ha ve three

Â different items, a, b and c. Whatever algorithm we have is going to, first, do a

Â comparison between two of the items. Let's say, there a and b. And then there's two

Â cases. Either it's yes or it's not yes, let's, let's say, they're distinct. And

Â there will be some code between the compares but either way then there is

Â going to be a different compare. If it's less than b, maybe the next compare is b

Â against c. And if you find that b is less than c and a is less than b, then you know

Â that they're in the, any algorithm that does that knows that the items are in the

Â order a, b, c. If b less than c goes the other way, then it takes another

Â comparison to determine the order. In this case, if c is less than b and a is less

Â than c then those three compares show that the order has to be a, c, b and if c is

Â less than a, then it's going to be c, a, b, those three compares that c is less

Â than a, c less than b and a is less than b. The only possibility is c, a, b. In

Â continuing on the right perhaps the next compare is a less than c and maybe if c is

Â less than a, then another compare, b less than c. So, in this case, if you go from

Â top to bottom in the tree with three compares at most you can determine the

Â ordering of the three different items. The idea of the lower bound generalizes this

Â argument to figure out a number of compares that you need for a minimum to

Â determine the ordering among N items. Now, the height of the tree, as I just

Â mentioned, is the worst case number of compares. Out of all the orderings the one

Â that's further stand in the tree that's the worst case and so the algorithm, no

Â matter what the input is, the tree tells us a bound, the number of compares taken

Â by the algorithm. And there's got to be at least one leaf for each possible ordering.

Â If there's some ordering that is not appear in a tree corresponding the

Â particular algorithm then that algorithm hasn't can't sort, can't, can't tell the

Â difference between two different orderings. So, the lower bound as a

Â proposition, that uses the decision tree like that to prove that any compare base

Â sorting algorithm has to use at least log base two (N) factorial compares in the

Â worst case. And by Stirling's approximation, we know that log base

Â two(N) factorial is proportional to N log based 2N. And then the proof is

Â generalizes what I talked about on the decision tree on the last side, slide. We

Â assume that the array consist of N distinct values there's a position created

Â that describes the performance of any algorithm to compare sequence done by any

Â algorithm to determine the N factorial different orderings. So, this three has to

Â have at least N factorial leaves and if the three of height h, it has utmost two^h

Â leaves. The only, the, the tree that has the most leaves of height h is totally

Â complete and that one has two^h leaves. And those observations give us the lower

Â bound. Two^h has to be greater than or equal to the number of leaves. And the

Â number of leaves has to be greater or equal to N factorial so that implies the

Â height of the tree has to be greater than or equal to log base two(N) factorial

Â which is proportional to N log N by Stirling's formula. That's a lower bound

Â on the complexity of sorting. So, we knew that the upper bound was N log,

Â proportional to N log N and we just proved that the lower bound is proportional to N

Â log N and that means that mergesort is an optimal algorithm. That's the first goal

Â of algorithm design is to try and find optimal algorithms for the problems that

Â we need to solve. Now, you have to take these results in context. Really what we

Â proved is that mergesort is optimal with respect to number of compares but we

Â already know that it's not optimal with respect to space usage. Mergesort uses

Â twice as extra space proportional to the size of the array it has to sort. And

Â simple algorithms like insertions or dump, they've they don't use any extra space at

Â all. So , what we want to take from these theoretical results is, is a guide when

Â we're looking at implementations and trying to solve practical problems. In

Â this example what it tells us, what theory tells us is don't try to design a sorting

Â algorithm that guarantees to use substantially for your compares than merge

Â sort. Say, one-half N log N compares. Is there a method that use one-half N log N

Â compares? The lower bound says, no. And that's a very useful thing because

Â otherwise, we might try to define such an algorithm. On the other hand, maybe there

Â is an algorithm that uses N log N compares and also uses optimal space. It's optimal

Â with respect to both space and time. And that's what we're going to look at soon.

Â The other thing is that the lower bound is for the particular model of computation

Â being studied. In this case, compares. It might not hold if the algorithm has more

Â information about the keys, for example, if it's known that the input is almost

Â ordered, we saw that insertion sort can be linear time for files that are almost

Â ordered. Or it's something about the distribution of key values if there are a

Â lot of equal keys we can get sorted, get it sorted faster than, N log N. And maybe

Â the way the keys are represented. We'll look at different methods that take

Â advantage of such properties. So, partially ordered arrays we may not need N

Â log N compares. Duplicate keys, we may not need N log N compares, we're going to look

Â at the method that I guess that down in linear time and a lot of situations. And

Â later on, we'll look at digital properties of keys where we can use digital character

Â compares instead of whole key compares and got a faster sort for certain practical

Â applications. Computational complexity is very useful way to help us understand

Â properties of algorithm and help guide our design decisions.

Â