# 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