# What is the work complexity for optimal merge using partitioning of sorted array of size n and p processors with segments of size n/p?

Using optimal method to find rank, we can partition a sorted array(size n) in segments of size n/p using p processors. The, we can find the rank of an element by placing a processor at the start and end of chunk, comparing it with the element for which we have to find rank, and repeat this process recursively until we arrive at the solution.

So time complexity will be O($$\log_p n$$) for an element. If we do this for n elements in parallel, using n processors, our time complexity will remain same but work complexity will increase to n*$$\log_p n$$.

However, I am getting this as a wrong result. The slide my sir has updated has work complexity of n/p. Please find the reference for the same in the below link, in the last 5-6 slides.

http://cstar.iiit.ac.in/~kkishore/aalg/Lecture2.pdf

Many thanks in advance!

• What approach to partitioning did you have in mind? Are you going to re-order the array when you partition it (e.g., by sorting or comparing to some pivot)? Or is the first segment just the first n/p elements of the array, the second segment is the next np/p elements, and so on? I encourage you to edit your question to clarify your approach. I also propose that you spell out more explicitly exactly how you will compute the rank of the desired element. – D.W. Nov 5 '19 at 18:06