News for hackers. Stuff that matters.
Re:Sort, sweep, and prune: Collision detection algorithms by spacecadet_ on Wednesday August 14, 2024 @09:04AM (#41245632)
You're right that it's not exactly n^2. For the i-th element we perform (n - i - 1) comparisons (indexing from 0). This adds up to a total of (n - 1) * n / 2 comparisons. (see https://en.wikipedia.org/wiki/Triangular_number)

In the end it doesn't make a difference for big-O analysis because it's used to describe the behavior when n approaches infinity, where the quadratic factor takes over.

There are no comments on this comment yet.