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.


Many thanks in advance!

  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 5 '19 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.