|
I think I failed to make my point clear - I was supporting your (Robbert's) proposition that the basic algorithm would be O(n), before further improvements.
The only circumstance I can see where the O(n*n) would apply is the one I quote above, finding number of players near each player.
You could look at one 'game loop' in this context, where you might need to construct n 'player views', each of O(n) approx, so the complete game loop computation is O(n*n), though even in this case I think O(n*p) is a better value.
As you said, there are various improvements that would reduce this in practice.
For example, if we have found when constructing Frank's view that Frank is near Ruprecht, we know when constructing Ruprecht's view that Ruprecht is near Frank and don't need to calculate it again .
Similarly if Frank is near Ruprecht, and Ruprecht is near Wilhelmina, we know that Wilhelmina is at least 'fairly near' to Frank, though we may need to refine that.
|