- #1
- 6,357
- 974
Remark: This is not homework
Given a vector a of permuted numbers from 1 to n, I want to construct the vector b which contains in the ith position the number of elemets of a_j with j <i which are larger than a_i. E.g.
a=(5,2,3,1,4), b=(0,1,1,3,1). Is there an algorithm which scales faster than O(n^2) ? I think yes, maybe a variant of mergesort or the like.
Thank you
DrDu
Given a vector a of permuted numbers from 1 to n, I want to construct the vector b which contains in the ith position the number of elemets of a_j with j <i which are larger than a_i. E.g.
a=(5,2,3,1,4), b=(0,1,1,3,1). Is there an algorithm which scales faster than O(n^2) ? I think yes, maybe a variant of mergesort or the like.
Thank you
DrDu