ChatGPT examples

[Alex Tweedly]

On 20/01/2023 16:52, Mark Waddingham via use-livecode wrote:
> On 2023-01-20 13:05, Alex Tweedly via use-livecode wrote:
>> We need a better algorithm. If we use a "linear scan", we can change
>> it from essentially Order(N**2) to approx Order(N).
>
> Slightly pedantic point (I appreciate that you did say 'approx')...
>
> Sorting can not be done in any less time than O(N*log N) - so the 
> revised algorithm is O(N*log N) as you have to sort the input for it 
> to be able to scan linearly.
>
I figured someone would pick me up on that :-) It was a pretty big 
'approx' :\)

The sorting step is indeed O(NlogN).

And the rest of it also worse than linear, but I don't have the math 
knowledge to even begin to think about how much worse. Quick testing 
says it's worse than O(NlogN), and in practice, it might even be as bad 
as something like O(N * sqrt(N)), guessing about the number of points 
within a (variable) sized window to the right of the current scan coord.

But in any "real app" usage that I can imagine, the 'clustering' effect 
would seem to improve it over O(N*sqrt(N)); e.g. if the points tend to 
cluster rather than be evenly randomly spread, then the number within 
the scan window goes down on average. "real app" could be players in a 
1st person player game, or vehicles on a road simulation, or (in 3d) 
stars in the universe - in all cases causing the minDist to decrease 
faster than when they are evenly spread.

Alex.