Follow US:

Practice English Speaking&Listening with: Lecture - 22 Average case Analysis of Quicksort

Normal
(0)
Difficulty: 0

Welcome to another lecture on Design and Analysis of Algorithms. Our topic for today is Average

Case Analysis of Quick Sort. Let us begin by discussing Average Case Analysis.

Let suppose A be an algorithm. Q is the set of input instances of A. And let us make it,

make Q be a function of n. So, Q of n is a set of instances of instances for algorithm

A of length n. T sub A of q is the time taken by A on instance q. Given this, you can define

the average time taken by A on inputs of size n, which we might write down as M sub A of

n. M could be interpreted as mean for example. And M sub A of n is defined as sum over all

instances in the set Q of n. Or sum over all instances of size n of the time taken by those

instances, divided by the total number of instances. So, this is the usual definition

of what we mean by an average. This is not the most popular definition of course. The

definition we usually use is the so called worst case measure. Here the worst case time

of an algorithm A on problems of size n, is defined as the maximum over all q of this.

The maximum time taken by any input instance of size n is defined as, the usual measure

or the worst case time. There are several reasons for doing this. Worst case is usually

easier to compute than this average. When we talk about the average, in some ways we

have to talk about all input instances. Whereas, often it is easier to deduce what the worst

instance is going to be. And, then we can just worry about that. For many algorithms,

most of the inputs behave like the worst input anyway.

So, in which case it does not really matter, it is not really necessary to take the average

in any case. Very often may be perhaps, the average case is easy to compute if at all.

And it might still not be preferable, it might still not be very popular because, in practice

we do not know which input instances are likely to appear more frequently. If some instances

appear more frequently, then in this mean expression we would have to wait those instances

more heavily. Therefore, if we just take the mean, then

that is not an indication of what might happen in practice. And therefore, again we do not

really focus so much on the average case analysis. Worst case on the other hand might be conservative,

but at least we know that it is conservative. And therefore, at least we can give some guarantees.

Our topic for today is quick sort however, where average case analysis turns out to be

quite useful and quite interesting.

So, let me say a few things about quick sort. Quick sort is a popular sorting algorithm,

perhaps the most popular and the most commonly used in practice. It is very fast. And as

I said, it is often the method of choice. The worse case time of quick sort is O of

n square. The average case time on the other hand is O of n log n and will see this quite

soon. So, in some sense the excellent performance

in practice might be better explained by the fact, that the average case time is O of n

log n rather than by focusing on the worse case time. So, let us now take a look at this

algorithm. Quick sort is based on divide and conquer strategy. And the algorithm is something

like this.

So, as input we take an array x 1 through n by writing x 1 through n, I simply mean

that x is an array whose length is n. This is an array in which we have keys. We can

think of these keys for the minute as some integers perhaps. And our idea and the goal

of quick sort is to sort them. That is let us say that the smallest keys have to come

at the beginning and the largest ones have to go towards the end.

We begin quick sort by looking at the best case first. So, the best case just checks

whether, this is an element this array has only one element. If it only has one element,

then the array is sorted trivially. And therefore, we just return that array. Otherwise, we pick

something which we will call it splitter. And that splitter is chosen to be the first

element of this x. The first key is the splitter. Then, we built three lists.

A list which will call small is going to be small, which contains all elements of x which

are smaller than the splitter. A list which we will call equal, which will contain all

elements of x which are equal to x 1 and so, we begin by putting x 1 into equal. I should

perhaps said less over here. But, will not we are not worrying, we are not very careful

about this. And we will not be very careful about this throughout the course.

So, we will I just tell you that, we have just made equal just single list, a list with

a single element. And we will also construct a list, which we will call large. And large

will contain all the elements of x, which are larger than x 1. So, right now it has

been initialized to null and small has also been initialized to null. This loop is simply

going to build up the lists, as we just described. So, first step if so for every element other

than the first. We check whether it is smaller than splitter

in which case, we add that element to small. If it is equal to splitter, then we add it

to equal. If it is greater than splitter, we add it to large. So, at the end of this

loop all the elements have been put into the proper lists. So, now it is simply a matter

of recursion. So, small is a list which contained all small elements. So, we call qsort or quick

sort in this list. So, as a result we will get these elements

sorted. Now, these elements are all guaranteed to be smaller than the elements in the list

equal. And those in turn, are guaranteed to be smaller than the list in large. But we

do not append large immediately over here, we quick sort it. So, as a result we have

a long list which is made up by appending three lists. But, which in turn is guaranteed

to be sorted. So, this is how quick sort works. So, as I

said it is divide and conquer strategy, the division part is where the interesting work

happens. And, then there is a conquer part and then the combined part is trivial. Correctness

is quite obvious here. You can do a induction on size, if you want to prove it formally.

And I will leave that as a easy exercise. So, now you wanted to analyze this algorithm.

Let me use T of n to denote the time for quick sort, on size and input. So, right now I have

only written n over here. But, I will actually have a specific input in mind. Just for the

minute. Later on we will worry about average cases or the worst cases or whatever. So,

right now let us say this is for a particular instance. So, T of n is the time taken by

that particular instance. So, how do we analyze this? Well.

Usually if we write something like this, we try to establish the recurrence. So, of course

no matter what input instance we feed. If it has length of only 1, then the time taken

is constant. So, that is what is you write down first. Then, we need to find out how

the recursion happens. So, let us just go back to the algorithm. So, over here the recursion

happens by calling quick sort on small and calling quick sort on large.

And before that, we have a loop which runs about n times. So, the result we have O of

n time for the loop. And T of large or T of the cardinality of large is the time taken

for that instance, for further for evoking quick sort on the list large. And T of small,

is the time taken for invoking quick sort in the list small. Now, we can analyze this

using the recursion tree. So, this was our basic recurrence. So, let us draw a recursion

tree corresponding to this.

So, we start off with the problem of size n. And, then as per this recurrence we break

the problem into two pieces. One is the small list and the other is the large list. So,

this is the small part and this is the large part. This is a problem of size n. This is

the small part, this is the large part. If this is the small part this is the large part,

then we are going to call quick sort recursively on these. So, furthermore this problem will

get split, this problem will get split. Of course, if the problem is going to get

split, may be one part one side could be smaller than other side could be larger and so on.

And may be one of the lists could be empty in which case of course, this whole thing

terminates. So, in general it is going to keep on splitting. May be once in a while,

a list terminates and things keep on going in this manner. So, what do we know all about

this.

Well, here is the first observation. So, if this node has size n, then we know that in

this node the number of keys which are going to be present is definitely going to be less

than n, in this node. Or in fact, in this node as well, so what does that mean? So that

means that as I go down from here along any branch, the size of the instance has to decrease.

So, which means I cannot go down too far. So, I start the instance of size n. It has

to decrease therefore, that means this height has to be utmost n. That is the first observation.

The second observation is that, if I look at any node its children have a certain size.

But, that size adds up to something strictly smaller than this. So, if I look at the size

over here, it is n the size over here has to be less than n. The size over here in fact,

has to be smaller than this for these two. And for these two, it has to be smaller than

this. So, this also has to be less than n. This also has to be less than n. So, if I

look at any level, the size of that the sum of the sizes of the problem at that level

have to be at most n. But now, if we go back to our problem our algorithm at each inside

the body of each invocation, we do work or we do work proportional to the size of the

problem. So, which means corresponding to each node

over here we are going to do work, which is proportional to its problem size. So, now

if I look at the total work done here, it is going to be O of n. Because, it is going

to be proportional to this problem size this problem size added up, it is going to be proportional

to O of n or it is going to be O of n. Similarly, here also it is going to be O of n. At every

level, it is going to be at most n at most proportional to n.

So, now we have an upper bound on the work. Because, there are n levels at most and at

each level the work is O of n. And therefore, the total work has to be O of n square. So,

this is the upper bound on quick sort. Now, I will leave it as an exercise for you to

construct an input instance for which, quick sort actually takes time n square. So, this

is actually fairly easy. Let me give you a hint, think of a sorted list.

What if the input instance is already sorted? But, the key question is that this is the

worst time. But, will it be the most time, will it take this long usually or is this

some kind of an unusual case. So, if you come back to the recursion tree to this tree, then

we know that at every level the work is going to be at most n. So, the real question that

we want to ask is, will the tree be of a large height or will the tree have a small height

because, if the tree has small height then our total work will be less.

So, in fact that is what we will see is, going to happen quite frequently. So, we did the

analysis of the worst case. So, let us ask what the best case is going to be? So, clearly

the best cases are the one in which tree is as small as possible.

If the elements that we are trying to sort are all distinct, then I will claim that the

height cannot be smaller than log n. Why is that? Well, I am going to leave this as an

exercise. But, again let me give a hint. So, we said as we go down the tree height must

decrease. But, we also said that the sum of the nodes over here, the size over here plus

the size over here must be smaller than this. But, if everything is distinct it will only

be one less than this. So, if it is one less than this, then you should be able to argue

that it would not decrease too fast either. So in fact, you should be able to argue that

it essentially halves at each step. And therefore, the total height will be something like log

n. So, what happens in the best case? So, in the best case it turns out. That the total

time taken will be O of log n, O of n log n. And in fact, there is a very simple situation

in which the best case will happen, which is this? If the splitter is equal to the median,

then the problem size halves. And, then the height becomes O of log n.

So, if the height is O of log n that I have taken as n log n, and that is the best. So,

we consider two cases one case in which the splitter goes, somewhere in the middle. Another

case in which the splitter was extreme, the splitter was the smallest element. Well, that

was supposed to be a homework exercise. But, suppose we take splitter, the splitter happens

to be the smallest element. Then, the list would be split very unevenly.

So, let us consider a case which is somewhere in between. So, in this the splitter is say

larger than n over 10 elements in the list and is also smaller than n over 10 elements.

So, it could be somewhere in the middle. So, of course this is an artificial case. But,

you can imagine that this will happen frequently enough because, after all if I pick an element

from a list, it is likely to be somewhere in the middle.

So, let us say this happens. Let us say that, every time I pick a splitter it satisfies

a property like this one. What happens then? Well, let us go back to the recursion tree.

So, let us redraw this recursion tree.

So, I start with an n node problem an n key problem. Now, I am going to pick a splitter

such that, it is larger than n over 10 elements. So, if I consider, what is the most uneven

distribution? What is the size? Well on one side I could get something like a list of

n over 10 elements. On this side, I could get a list of say 9 n over 10 elements. So,

this is good because, this list is going to shrink and its going to terminate quickly.

The height is going to be small over here. This on the other hand, might appear to be

a problem, because here the height has not reduced. That the size has not reduced. If

the size has not reduced, then it will keep on going in this manner. And may be the height

of the tree may be large. But, what we argued was the work done in this algorithm is, the

height of the tree is at most the height of the tree multiplied by n because, n is the

work at each level.

So, let us see what happens? So, in the first level as we have pointed out, the largest

problem size will be 9 n by 10. It could be smaller than that. So, it could be say half

half. But, that is actually not so bad. That means, the third tree height will be actually

small. So, this is trying to force the tree height to be large. And therefore, it is trying

to force quick sort to take large, to take long time. So, we are sort of looking at we

said that we are looking at neither the best nor the worst cases.

But, we are sort of erring on the side of the worst within this region. So, in the first

level problem, largest problem level size is 9 n by 10. What happens next? Again, we

assume that the problem will split in the ratio 1 is to 9. So, this will become say

something like n by 100 and 9 n by 100. This will become something like 90 n by 100 and

81 n by 100. So, as you can see this rightmost branch will keep on having the largest size.

So, what will happen? At each in each step, the size of the largest problem drops down

by a factor 9 by 10. And therefore, we can conclude that log of n to the base 10 by 9,

the problem size will even on this right most branch will drop down to 1. And even to do

that, I will take log of n to the base 10 by 9 levels. So, this is good news in the

sense that, even when I am looking at a split which is lopsided.

The number of levels, the height of the tree is still going to be about log. Well, it is

going to be log not to the base 2. But, to the base 10 by 9 and let me just remind you

that, log n to the base 10 by 9 is simply equal to log of n to the base 2 divided by

log of 10 by 9 to the base 2. So, this is still only a constant. And therefore, this

is still O of log n. So, the height given in this case is O of log n, the height of

the tree. The tree height is of log n. And therefore, the total work is n log n.

So, even in this middle case we have seen that the total work is about n log n. So,

that is the sort of the first intuition as to why quick sort should work? Quick sort

may be works while in practice. Because, unless the splitter comes from too large or too small,

the two sub problems that we create will be reasonably balanced and not too lopsided.

And if they are not too lopsided, then the height of the tree height of the recursion

tree will not be too large. Next we are going to actually do sort of a

very systematic analysis, of the average time taken by the quick sort. We are going to do

this in two ways. In one way, we are going to derive the recurrence. And we will not

really solve the recurrence, but I will indicate to you how that recurrence could be solved.

And it will turn out that, the solution of the recurrence is n log n. And, then I will

indicate somewhat more elegant way using, which we can also derive n log n.

So, when I talk about average case, I have to define what are the possible inputs? So,

in this case I am going to assume that, for this particular analysis I am going to assume

first of all that all the inputs are distinct. All the inputs, the numbers the elements the

keys which are given to us are all distinct. And if they are all distinct, I might as well

assume that they are integers 1 through n for each of the n keys.

But of course, they will not be given to me as 1 through n, but they will be given to

me as some permutation of 1 through n. So, now I will state exactly what my allowed inputs

are. So, my allowed inputs are any possible permutation of the integers 1 through n. So,

there are n factorial possible permutations. There are that many input instances for my

algorithm. So, my question will be, what is the average time taken by my algorithm over

all these input instances or over all these permutations?

And of course, I would like you to express it as a function of n. So, now I am going

to express I am going to look at our analysis. And I am going to figure out, how we can estimate

this. So, although I have been talking about different, about taking averages I can also

think of this in terms of probabilities. So, I can think of this as follows. So, I have

been given a set of input instances. I have constructed a set of input instances.

And I am picking one of those instances at random. And I am doing this, giving equal

probability to every input instance. So, there are n factorial instances possible. Each one

has equal probability or in other words each one has probability whenever we assign. So

I am picking one of those. And I could also be asking under this choice, what is the expected

time for that for the instance that I pick? Which is of course, the same thing asking

what is the time taken, what is the average of all the times?

So, now this average can be estimated by grouping the instances into separate groups. And, then

calculating the average within each group and then multiplying by, essentially by the

size of the group or by the probability of picking that group. So, here is how you are

going to do it. So, in the first step of the algorithm, we pick a splitter. There are n

keys and the keys are going to be numbers in the range 1 through n. So, there is going

to be some probability that, the splitter is going to be one of these keys.

It is to be even any one of those keys. So in fact, let us assume that we always pick

a splitter at the first element which is in fact, what the algorithm did. So, in that

case the question is. So, we are splitting all our input instances into those permutations

first in which the splitter in which I appears in the first place. And within that group,

we are taking the average time. So, let me draw this picture out here.

So, here is our set of input instances. So, I am breaking it into pieces. So, these are

input instances which begin with 1. That is, they have 1 in the first place. These are

input instances which begin with 2. These are input instances which begin with 3. And

somewhere over here are input instances which begin with i. And of course, at the end there

are instances which begin with n. So, I am going to pick a group.

And, then I am going to pick an element from it. Or I can ask, what is the average time

taken for this group? And if all this groups are identical, then I can just take this average

or I will have to wait with the size of this group. So, that is exactly what I have done

over here. So, I have taken the average time for this group which is what is written over

here? Average time given that splitter is equal to i.

But, given that splitter is equal to i is the same thing as saying, that the first element

of the list is i. So, I am in this region of my input space. And since, I want the average

over the entire space, I just want to I just multiply by the probability that the splitter

is equal to i. Or the fraction which indicates how many instances are there in this group

as compared to the entire group. So, this is what I get.

Now, what is the average time given that the splitter is i? Well, if we go back to our

algorithm here. So, I pick a splitter over here. Then, I am going to have this loop anyway.

So, if I am solving a problem of size n, I will do n work in any case. And, then I will

have my inputs split into two lists or three lists. But, only two of which will be interesting.

So, average time given splitter i is going to be O of n for that loop to take, loop to

do its work plus the average time for sorting the small set.

But, what is the small set? It is the permutation of the elements of integers 1 to i minus 1.

And the average time for sorting permutation of elements i plus 1 through n. Because, that

is what quick sort does. It splits into groups, it sorts the first group, takes the equal

elements in which case in this case there is only one equal element which is i. Sorts

the last group and then concatenates them together.

So, in addition to sorting the time will require is O of n. So, you might require O of n time

also for concatenation. But, in any case we have written O without actually mentioning

the constant. And therefore, this is fine. Or we might have a clever data structure in

which case, we do not need this O of n time. But, in any case we need the O of n time for

the loop. So, this is perfectly fine. So, now you have the average time for sorting

permutation of 1 through i minus 1 and then the average time for sorting permutation of

i plus 1 through n. Here is the important part. So, the first time we picked the splitter

to be i and then we constructed this group. But, the key observation has to be, that the

numbers the order in which these numbers will appear is not going to be particularly biased.

So, we know that within the group that we selected, i is going to appear as the first

element. Since we are dealing with all possible permutations,

the other elements would appear equally likely in the first space in this group or in the

second space in this group or in the third space in this group. So, this group will have

all possible permutations of 1 through i minus 1 as well. So, if it has all possible permutations

of 1 through i minus 1, then the time average time for sorting it will be T of i or other

T of i minus 1. It does not really matter, T of i over here.

The time over here is going to be i plus 1 through n or it is going to be T of n minus

i. So, I think. So, what do we get from this? Well this expression has to be put in over

here and as a result we get something like this.

T of n is equal to sum over i of this probability that, the splitter is i. There are n choices

for i and since we are considering all possible permutations. Everyone is equally likely to

appear in the first place. And therefore, the probability that i appears in the first

place is just 1 over n. So, this is 1 over n and this we just established is this. And

that is what I have written over here. I just remarked that this should have been

i minus 1. And that is what I have put in over here. Now, this recurrence can actually

be solved. It is a little bit tedious algebraically, but you can certainly solve it by recursion

induction. Since I am telling you that, the solution is n log n. So, that will establish

that the average case of quick sort is n log is O of log n.

Now, we are going to do we are going to consider an alternate method for solving this. So,

this is going to be much more direct. We are not going to write recurrences. We are just

going to do some interesting counting. So, here we will focus on the comparisons performed

by the algorithm. So, after all the important operation in all of this, is comparison. So,

if you go back to the loop let us just take a look at that. We did other work as well.

Say we added elements into lists. But, corresponding to every such operation there is a comparison

operation going on as well. So, certainly if we bound the number of comparisons, then

that will give us a good indication of the time taken by the entire algorithm. So, that

is exactly what we are going to do. So, we are going to estimate what is the number of

comparisons performed by the algorithm on the average.

And we will show, then that is going to be something like O of n log n. Well, let us

first determine what is the maximum number of comparisons possible? So, the maximum number

clearly is n into n minus 1 upon 2. This is, if every key is compared with every other

key. And of course, if the input is the worst case input, then something like this actually

happens. But, this will not this will, but if the input is some permutation, then every

key will not get compared with other key. So, just to see clearly what is going on,

I am just going to describe a table which shows what happens for different input instances.

So, a table this table will have rows. And there will be a row corresponding to every

possible comparison. So, our keys are integers in the range 1 through n. And for every i

and j, we will have a row. So, I compare j that will be the label of that row. And in

that row, we will have information about whether i and j are compared in every possible input

instance. And in fact, the columns will be the input

instances. So, the entries are going to be indexed by two indices, one is i colon j.

Well, this itself is a complicated index and the other is this permutation P. So, here

for example, is a table. Of course, I have just made up the entries, just to tell you

what this table might look like. So, the rows are labeled i colon j. So, starting with 1

column 2, 1 compare 2, 1 compare 3 and so on to n minus 1 compare n.

So, during the execution whether it is or not 1 is compared to 2, when permutation 1

is input is going to be written out here. So, you have left a blank over here. And that

just says that node, that node will not be compare. It is just an example. On the other

hand, 1 and 3 will be compared, when permutation 1 is the input. Similarly, if permutation

2 is the input then 1 and 2 will get compared, 1 and 3 will get compared and may be some

other things will also get compared. Similarly, there will be other permutations

for which this will be the pattern of comparison, this will be and so on. So, there are n factorial

possible input permutation. So, we have n factorial possible columns. And for each possible

comparison, we have a row. And their intersection says that, whether that comparison actually

happens in the corresponding execution.

The key question is, Are there many T cells in this or are most of the cells blank? What

we really want to know is, what fraction of the cells in the column are marked? Or what

is the average number of cells which are marked in a given column? We are not going to answer

this question directly. We will begin by asking, what is the fraction of cells which are marked

in any row? And interestingly, that will tell us something

about what happens in columns as well. Say, if I go to a particular row of this table

or the row which has labeled i colon j, the question that I am asking is, Is i going to

be compared with j in the first permutation or in the first input instance or in the second

input instance in the third input instance and so on.

So, here is the key observation for i to be compared with j either i or j must be chosen

as a splitter before, one of the elements between that is elements i plus j or j minus

1 gets splitter. So, let me explain this a little bit.

So, here is i here is j and there are some elements in between. Well, I know i plus 1

i plus 2 all the way till j minus 1. So, these are the elements that I am considering. Of

course, they will not appear in my input instance in this order. They will be in my input instance,

they will be scrambled up. But, I am just thinking of them as sitting in a line. Now,

suppose some element over here gets picked up as a splitter, what happens?

If this element is picked as a splitter, then this element is compared with everything else.

If everything else is compared with it, then this I will get input in the small list. So,

i will go into the small list. j on the other hand will get input in the large list. But,

remember that once an element goes into this list and another element goes into another

list, there is no question of comparing them subsequently.

So, if any of the elements in between over here get picked as splitters, before any of

these two elements get picked. Then, we know for sure that these elements will go into

separate lists. And therefore, they will not be compared. On the other hand, before these

elements have been picked suppose i gets chosen, what happens then? Well, then i is going to

be compared with everything larger than it, or certainly everything which has not been

found which is in the current list. But, if nothing in this has been selected

as a splitter, then this had been better been in the current list. And therefore, j will

get compared with i and vice versa. If j gets picked first, then i will get compared because

j will be compared with everything over here. So, which means that, these two elements must

get split as splitters before these, inner elements are picked. So, what is the probability

of that happening?

So, I claim that probability of i or j being chosen before i plus 1 or before elements

i plus 1 through j minus 1 is in fact, 2 minus 2 upon j minus i plus 1.

So, here is i here is j. So, how many elements are these in total? These are j minus i plus

1 elements. And out of these, the comparison happens only if this is picked or this is

picked. So, there are two cases which are good out of j minus i plus 1 cases. And therefore,

that is the probability. So, now actually things are very, very simple.

So, the fact that i or j is probability that i or j is chosen, before i plus 1 through

j minus 1 is this just tells us something very simple. It tells us that the fraction

of T s in this row is just this. Because, that is what the probability is. We are going

to pick a row at random. And we know that, 2 upon j minus i plus 1 fraction of the time

we get a T or the comparison happens. So that means, in other words the number of

columns the fraction of the number of columns in which T s appear, is just going to be this

much. So, what does that tell us? So, it tells us that the total number of T s in the entire

table is going to be sum over all the rows of this multiplied by n factorial. Let me

explain that a bit slowly. So, from this what can I conclude?

I can conclude that, in row i colon j contains n factorial times 2 upon j minus i plus 1

T s, what T s represent? Where comparisons happen, whether comparisons happen or not.

But, if I want over the entire table I just have to sum over all possible rows. So, this

is what I have written out here.

Except that the n factorial has taken outside because, it does not depend on what row I

am looking at. Well, this expression can be written out slightly differently. So, all

possible labels i j, I can now classify as all possible levels in which j is a second

element. And, then the first element has to be smaller. And therefore, it is sum over

i is less than j of this expression. But, what is that, so summation over i of

i less than j of this expression, well. What is the first term? So, i begin from 1 and

so, first term is simply 2 upon j. And next term is 2 upon j minus 1 and so up on until

2. But, what is this? So, this is let me write it down again.

It is 2 upon j plus 2 upon j minus 1 plus all the way till 2 upon 2 or written differently,

it is 2 times 1 plus half plus one third all the way upon till 1 upon j. And this we know

simply l n n by treating this sum to an integral, converting it to an integral. So, this is

a good estimate or in fact, this is an upper bound.

So, finally we have this whole thing as n factorial times sum over j of O of l n j.

But, if you are going to take the sum over j, what do we get? Well, we get n l n and

n. So, we get n l and n over here, what is n l and n? So, we have total number of T s

in the entire table list n factorial times n l n n. So, what then is the number of T

s per column or what is the average number of T s per column?

Well, how many columns are there are there? There are n factorial columns. And therefore,

we divide this total number by n factorial and then we get O of n l n n. So, average

running time is O of n l n n and why is that? Because T s represent the number of comparisons,

and we said that the average that the time is in fact proportional to the number of comparisons.

So, the average running time is going to be O of n l n n.

But, O of n l n n is simply O of n log n as well. So, here the base was the natural base

was e or this was the natural logarithm. Here the base is 2, but that does not matter log

of n and l n of n are within a constant factor of each other. So, let me conclude. So, I

would just like to say that, a similar idea works for selection as well. So, suppose we

want to select the rth smallest element, then something like this will also be fine.

Thank you.

The Description of Lecture - 22 Average case Analysis of Quicksort