Algorithm for creating a large number of points in Java

I am trying to design an algorithm that creates random points in a square.

The problem is: if we have a mxm square, we randomly create n points with 1 < n < m²

The algorithm has to be efficient, that means if m = 500, we can have either n = 1000 or n = 100 000. And the cost of the algorith开发者_开发知识库m must be the same. So m should not be a factor of the cost.

I really don't know what to do... I frist though about doing this:

for (int n = 1000, n > 0, n--) {
create a point
}

But this way m is a factor of the cost...

Do you know any algorithm that could help?

Thank you

Matt

---

Your requirements sounds impossible to me.

You say that you need to create n points, where n will be any number from 1 to m^2.

It should be clear that if m grows, the probability of getting a higher n increases. So, as m grows, the number of points (n) you will create must grow.

Creating a point is constant time, and independent of any other points created. So, as n grows, so will the work required to generate n points.

Using Big Oh though, the following algorithm will take O(m^2) time to create n points:

Random r = new Random();
int m; // something
int n = r.nextInt(m*m-1) + 1; // random number between 1 and m^2
for(int i = 0; i < n; i ++) { 
    // create a random point in the square 
    Point p = new Point(r.nextInt(m), r.nextInt(m));
}

---

My guess here is that the algorithm will always be O(n) as a worst case. The assumption here is that your professor is using the definition of Big-O being the worst case, not the best or average case performance. Therefore I do believe that m is always what will be the factor, regardless of what it is.