Running Time Analysis (optional)

Loading...

From the course by University of California San Diego

Algorithmic Toolbox

3366 ratings

University of California San Diego

Algorithmic Toolbox

3366 ratings

Course 1 of 6 in the Specialization Data Structures and Algorithms

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

From the lesson

Divide-and-Conquer

In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. You will even learn that the standard way to multiply numbers (that you learned in the grade school) is far from the being the fastest! We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice. Finally, we will show that these two algorithms are optimal, that is, no algorithm can sort faster!

Random Pivot13:04

Running Time Analysis (optional)15:32

Equal Elements6:31

Final Remarks8:12

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

In this video we are going to prove formally

an upper bound on the running time of the randomized quick sort algorithm.

Namely we're going to prove that the running time on average of

the randomized quick sort algorithm is n log n.

That is it must be go for n log n.

And that is, that, in the worst case, the running time is big O of n squared.

Well, before going into the details of the proof.

Let's again, intuition.

First of all, let's know that what we need to estimate is the number of comparisons.

Why is that?

Well because a quick sort algorithm contains

of first the call to the partition procedure and then to recursive calls.

Each of these two recursive calls is going to be unwinded into

the call to partition procedure and another to small recursive calls.

So what is going on inside the quick sort algorithm is essentially many calls

to the partition procedure.

While inside the partition procedure, what we do actually is to compare

all the elements of the curve and separate who is the pivot element, right?

So what we estimate is a total number of comparisons.

Which is not surprising because the quick sort

algorithm is a comparison based algorithm.

Well, now let me also explain why balanced partitions are better for us.

I will explain this intuitively.

So consider this story example.

This array of size seven.

Assume that we selected one as the pivot element.

So we partitioned the rate is shown here on the left.

Now let's see what we now know.

We can pair it all the elements in this array to the pivot element

which is one in this case.

So now we know that one, the final position of

the pivot element is just the first position in the array.

So we known that 1 is the minimum value.

However, we know nothing about pairs of other elements, right?

So we only learn that 1 is the minimum value.

Now consider another possibility,

consider the following balanced partition shown on the right.

So assume that we selected 4 as the pivot element.

I claimed that in this case, this partition is much better for

us because we saved many subsequent comparisons.

So look, in this case, in the subsequent trends of the partition precision,

we are not going to compare elements 3, 1, 2 with element 6, 5, 7.

Because we already know that all the elements to the left are for a.

As in all the elements to the right are formed.

Well the left part will stay in a separate recursive code and

the right part well stay in a separate recursive code.

So once again, balanced partitions save us a lot of comparisons

that we do not need to make in the subsequent calls to partition procedure.

Another thing I would like to discuss with you before growing and

know details of the proof is the following.

Our algorithm is randomized, so its running time and

its number of comparisons depends on the random beats used inside the algorithm,.

In particular for

any two elements there is some probability that they are going to be compared.

And using this toy example shown on the slide,

I would like to just build an intuition on how to estimate

this probability on which factors this probability depends.

So consider this small example.

So this is an array of say it's nine containing all the digits.

And I would like to estimate the probability that elements 1 and

9 are going to be compared if we call randomized quick sort physics already.

So, let's see what happens.

Assume that in the very first quarters of partition procedure,

we select the elements 3 for example as the pivot element, so what happens?

In this case, 1 will go to the left of 3 and 9 will go to the right side.

To the right of three, I'm sorry.

So in this case 1 and 9 will be in different parts and

they will never be compared in

as a partician procedure just because they are already in different parts.

Okay, for the ways it means, that we already know that 1 is smaller than 9,

because 1 is smaller than 3, and 3 is smaller than 9, right?

We do not need to compare them.

Well then this happens if we select as our pivot element, any of the elements,

2, 3, 4, 5, 6, 7 or 9, 8, I'm sorry.

If on the other hand we select 1 and 9 as our first pivot element,

then 1 and 9 will become pivot.

Just because, well, if we select, for example, 9 as the pivot element,

we can pivot with all the elements of our array, in particular with 1.

So there are two cases when 1 and 9 are compared.

And this is how exactly the case is when either 1 or

9 are selected as a first pivot.

In all other seven cases there are not compared.

This means that the probability that they are compared are 2 over 9.

Okay, makes sense?

Now let's try to estimate the probability that the elements three and

four are compared.

Well I claimed that in this case this probability is equal to 1.

And the explanation is the following,

there is no element inside RRE that can help the randomized

weak sort algorithm to understand that 3 is smaller than 4 without comparing them.

I mean for 1 and 9, there are seven such elements.

All they are is elements.

I mean, if we partition with respect to any of the elements,

we already know that 1 is smaller than 9 because they go to other parts.

Different parts with respect to this pivot.

For three and four there is no such element.

So algorithm just must compare these two elements

to be sure that 3 is smaller than 4.

So in this case the probability is 1.

Well this shows that the probability of comparing two elements

depends on how close they are in the sorted array.

In particular if they're very far apart of each other than the probability

is small and if they are close to each other than the probability is high.

We will use this observation in the formal proof of our statement.

We now start to formally prove an upper bound

on the running time of the randomized quicksort algorithm.

For this, we introduce the following random variable.

Let i and j be different indices from 1 to m.

We define Xi of ij to be equal to 1 if two elements, A'[i] and

A'[j] are compared in the [INAUDIBLE] quick sort algorithm and

to be equal to 0 otherwise.

Once again, to estimate the running time of the quick sort algorithm,

we would like to estimate the total number of comparisons made, so we would like to

estimate, for any pair of elements, what is the probability that they are compared?

As we discussed on the previous slide, the probability that two elements

are compared depends on how close they are in the sorted version of our array.

For this reason, we define c of ij dependent on the sorted array.

We do not have this sorted array, right?

We are only constructing this in the quick sort algorithm but

we use it just for the analysis, okay?

The next thing to note is the following.

For any two elements of our initial array assorted array doesn't matter, so for

any two elements they are either compared just once or they are not compared at all.

So, why is that?

Why just once?

Well, if two elements are compared at some point,

this means that at this point one of these elements is because in the partition

procedure we can put a with all of the elements of the current summary.

So, if two elements are compared that one of them is a pivot.

This also means that right after the call of this partition

procedure, we are not going to use this pivot element.

We will put the pivot element into its final place, and

we are not going to touch it in any of the subsequent calls.

This immediately implies the quadratic upper bound

on the worst case right in time with final algorithm.

Once again we have quadratic number of possible pairs of element, and

each pair of element is as it compared once or not compared at all.

Right so right in time with the worst case is quadratic.

Now comes the most important observation of this proof.

I claim that the elements A'[i] and

A'[j] are compared if and only if

the first pivot selected in the subrange of the solitary a prime

from either side to index j is either a prime of a, of i, or a prime of j.

Well let's see why.

First of all, when we select it pivot the random pivot which is not in

their sub range, and then all the elements from this sub range in this

sort of element goes either to the left or this to the right.

So, they all stay together in the same branch of three, okay.

So before we select a pivot which stays inside this range,

all these elements stay together in the same sub-array.

Now, assume that we selected a pivot from this sub-range, and

assume that it is not A'[i] or A'[j], for example.

In this case a prime of A and a prime of J will be splitted apart.

They will go into different parts with respect to this pivot, right?

At this point I must humor that all the elements in my summary are different,

and in duality are different, okay?

So once again, if the first selected element

from this subrange is not prime of A or

a prime of j then these two elements are not going to be compared.

Because right after the partition procedure uses this pivot

from this range A prime of a and A prime of j will go to different parts, right?

If, on the other hand, the first selected

pivot from this subrange is either A prime of a or A prime of j,

then these two elements are going to become paired, right?

So this is the most important observation in this proof.

Everything else is just calculations.

So if this is clear, let's then estimate

the probability that second respondent to elements are compared.

So we know that they're compared if and

only if the first selected Pivot in this sub range is one of these two elements.

This helps us to estimate the probability of

not the fact that c of i j is equal to one.

Well this is equal to two.

I mean because we have only two choices.

I mean either a prime of a, or a prime of j divided by the total number of choices,

I mean the total number of elements in this subrange.

And this is j minus i plus 1.

So the probability that Z of ij is

equal to 1 equals 2 divided by g minus i plus 1.

For example, if j and i differ by 1.

So j is equal to y plus 1.

So neighboring element in the.

Then this probability is equal to 2 divided by 1 plus 1.

This is 2 by 2, this is 1.

[INAUDIBLE] Just reflects the fact that if there are two neighboring elements inside.

This sorted array, then the algorithm just must compare them,

to understand that one of them is smaller.

There is no other element that can help our algorithm to realize

that one of these element is smaller than the other one, okay.

This in turn helps us to estimate the expected value of this random variable.

So recall that if we have a random variable, which takes only values zero and

one, then its expected value is one multiplied by

the probability that it takes

value one plus zero multiplied by the probability that it takes the value zero.

Well zero multiplied by something is zero.

So what is left is just probability.

That it takes multiplied by one.

So the expected value of CIJ is equal to 2 divided by g minus i plus one.

The final step in our proof is estimating the sum

random variables to see they all possible I and J.

So, once again the expected value of average value

of the sum of the number of comparisons made is the expected value of the sum

of all possible x adjacent, or for all I Js.

So the expected value of their sum is the sum of their expected values.

So we can write the following.

The average running time is equal to the sum overall possible

different of the expected values cij, and

we know this expected value already.

So this is a some overall possible different ij,

in where j is greater than i of 2 divided by g minus i plus one.

Well we can take this constant two out, and consider all the possible.

And consider a fixed i.

For this i what we have j ranges from i+1 to n.

So what we have for the specified time in this sum is a subset

of the following sum, 1/2+1/3+1/4 and so on.

And this is actually a known sum.

This is called harmonic series and it is known that it grows arithmetically.

Once again, 1 over 2 plus 1 over 3 plus, and so on,

1 over n, is theta of logarithm of n.

Well, this means that, for each they correspond in sum, which

ranges over all j from i plus 1 through n, grows, at most, logarithmically.

This means since we have m traces for

i from one to m that the grows vertically as m.

Okay, and this concludes our proof.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play