The correct answer to this quiz is the third option.

In fact, it's actually quantity n-1 / 2, not n/2.

But, basically, half the elements.

Again, this sort of a sneaky way to see this if you want.

Which is that, clearly, the two recursive calls are symmetric.

The expected value of the left recursive call is going to be the same as

the expected size of the right recursive call.

The two recursive calls always comprise n-1 of the elements.

Because they're symmetric, you expect half in each.

So n-1 / 2 in each.

Though for this problem, I think it's perfectly fine just to compute this

using the definition of expectation.

If we let X denote the random variable that we care about, the subarray size.

Then we can just compute directly by summing over all of the possible outcomes.

All of the possible choices of the pivot.

With probability 1/n, we choose the minimum of the pivot.

Resulting in 0 elements being passed to the first recursive call.

With probability 1/n, we pick the second smallest element.

Resulting in 1 element being passed to the first recursive call.

With probability 1/n, we pick the third smallest.

Giving us a subarray size of 2.

And so on.

With probability 1/n, we pick the maximum element.

Giving us a subarray size of n-1.

If you just compute this sum out,

you will get, as expected, n-1 / 2.

Expectation is the last definition that I'm going to give you in this part one

of the probability review.

Next, is our fifth and final concept for this video.

Which is Linearity of Expectation.

That's not a definition.

That's more of a theorem.

What is linearity of expectation?

This is a very simple property of random variables that's super-super-important.

This comes up all the time when we analyze randomized algorithms.

And random processes, more generally.

What is linearity of expectation?

It's the following, very simple claim.