The complexities don't multiply here. The complexities would only
multiply if you had to sort for EACH of something. We're only doing a single sort.
sorting the points along one axis which already gives O(nlog(n))
You're looking at it backwards, this is actually good news! It means that any subsequent work we do of similar or lower complexity doesn't change anything.
I never said that. I just mentioned that O(n log(n)) is the lower bound since sorting will already take that long.
What I'm concerned with is the complexity of the scanning step, which I think might be more than O(n log(n)) on its own (and therefore more than O(n log(n)) overall)
At least I'd like to see an explanation why it's <= O(n log(n))
Comments
The complexities don't multiply here. The complexities would only multiply if you had to sort for EACH of something. We're only doing a single sort.
You're looking at it backwards, this is actually good news! It means that any subsequent work we do of similar or lower complexity doesn't change anything.
I never said that. I just mentioned that O(n log(n)) is the lower bound since sorting will already take that long.
What I'm concerned with is the complexity of the scanning step, which I think might be more than O(n log(n)) on its own (and therefore more than O(n log(n)) overall)
At least I'd like to see an explanation why it's <= O(n log(n))