Consider the quadratic expression:
achieves a maximum over 
when
or
.
If then we
have
Therefore, 
If 
then we
have
Therefore,
Alternative solution using derivatives:
achieves a maximum over when
or
.
Clearly we can say that by the expression achieves a
maximum over the parameter’s range 
at either
end point, means or
as
can be seen since the second derivative of the expression with
respect to q is positive.
First derivative of 
Second derivative:
If 
Which is greater than 0 i.e. positive
If 
which is also greater than 0 i.e. positive
So, that we can easily say that expression
achieves maximum over
The running time of RANDOMIZED-QUICKSORT depends on the number of calls n to PARTITION and X i.e., the total number of comparisons, between pairs of elements in an array A of size n.
The expected running time of RANDOMIZED-QUICKSORT is
can be shown
by first showing, 
.
Let the elements in array A in increasing order of value be,
z1 < z2 < · · · < zn. This is only for the purpose of analysis.
For 1 ≤ i < j ≤ n, let 
to be the
set of elements between 
and
of
the array A.
The indicator random variable,
is used to
calculate the lower bound on the number of comparisons.
Take expectations of X on both sides and use linearity of expectation. Then,
Hence, the expected running time of RANDOMIZED-QUICKSORT is
.
In QUICKSORT algorithm, the expected running time is 
as the
recursion stops at level 
. There will
be 
subarrays of size k in the resulting array.
The INSERTON-SORT takes 
time to sort
the entire array. This is equivalent to sorting each of the
subarrays of size k .
Thus, this sorting algorithm runs in the 
expected
time.
The value of k must be chosen in such a way that it does not
exceed the expected running time 
of
QUICKSORT.
If it is chosen very big, then the cost of insertion 
will be
greater than
. Hence, k
must be between 1 and 
.
