Calculate the parallel quicksort analysis for average case Work,

In the analysis of parallel algorithms, the work efficiency is often expressed in terms of the work function W$($n$).$

For parallel quicksort, let's denote:

$W(n)$ : The total work $($computation$)$ done by the algorithm on a problem of size $n.$

For parallel quicksort, we can use the following recursive expressions for $W(n)$

Work Function $W(n)=\{\begin{array}{ccc}0,& if& n1\\ n+W(& \text{l}\text{e}\text{f}\text{t})+W(\text{r}\text{i}\text{g}\text{h}\text{t}),\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

In the above expressions, "left" and "right" refer to the sizes of the two partitions created during the partitioning step, for Average Case this can be $\frac{n}{2}.$