Okay, so in this case, if this happens at this iteration,

I mean at this call to partition procedure,

then we can write the running time of our Quicksort algorithm,

satisfies the following relation T of n is equal to n plus t of n minus one.

The term n here, the response to the running time of the petition procedure.

Well, it is actually big often.

But just to simplify let's put n here.

Let me also recall you that, well if we have an array of size n,

then the partition procedure indeed works in time,

big often, because it just becomes the subarray?

So now let's see what is the solution for this recurrence relation.

Well, we can just unwind this recurrence relation term by term.

So we have n plus T of n minus 1.

Let's replace T of n minus 1 by n minus 1 plus T of n minus 2.

Then we replace T of n minus 2 by n minus 2 plus T of n minus 3.

And we keep doing so.

So what is left is the following sum, n + (n- 1) + (n- 2) and so on.

So what we know is this sum already, so this is arithmetic series.

And we know that it grows quadratically.

Which give us something strange,

I mean our Quicksort algorithm works in quadratic time.

Which means that it is not quick, actually, right?

We'll resolve this issue later.

Now, let's consider a slightly different case.

Assume that somehow, we always partition into two parts,

such that one of them has size, for example, n- 5.

And the other one has the size four.

Well I claim that even in this case.

First of all, note that both these cases correspond to very unbalanced partitions.

In the first case, we have two parts one of size 0 and one of size n-1.

In the second case, we have two parts one of size five.

And one of size four and one of size n minus five.

So the size of stuff parts are very unbalanced.

They are very different.