#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Finding the proper Algo (2D sorting)

Member Posts: 1
I am supposed to create an O(n(logn)^2) algorithm wich, given as input a sequence S of points in the two dimensions (each point is discribed by a x value and a y value) the algorithm sould give or each point:

the number of elements from which each point is strictly bigger( both x and y bigger)

any help or idea would be appreciated!

• Member Posts: 129
I'd start with applying some standard sorting algorithm first to arrange points by x value. Sort these by using two memory buffers and splitting the original array bit by bit into those two arrays and merging them to original (can't remember the name of the algorithm, sorry) if x and y are simple floating point or double, that would give O(n*sizeof(x)*8). Then I think you can simply count the number of points Pj for each point Pi where Pj.y>Pi.y (j>i). I am not entirely sure if the complexity for this operation would be O(n(logn)^2), but it should be close and the result would be O(n*sizeof(x)*8) + O(n(logn)^2) which is roughly O(n(logn)^2) when we leave out the linear complexity of first operation. I may be wrong though, it's been a while since I have thought of any such algorithms and especially in terms of complexity.

: I am supposed to create an O(n(logn)^2) algorithm wich, given as
: input a sequence S of points in the two dimensions (each point is
: discribed by a x value and a y value) the algorithm sould give or
: each point:
:
: the number of elements from which each point is strictly bigger(
: both x and y bigger)
:
: any help or idea would be appreciated!
: