News for hackers. Stuff that matters.

A comment on The skyline problem. Parent comment

Re:The skyline problem by michaelmior on Tuesday September 02, 2014 @09:16PM (#8261085)
I'm not sure what you mean by the pyramid-shaped configuration. In any case, n queries taking log(n) + n time each is O(n log n). I think you're right that a range tree should work fine.
[ Parent | on HN ]
Re:The skyline problem by brianpgordon on Tuesday September 02, 2014 @10:26PM (#8261246)
I mean this thing from the article:

https://briangordon.github.io/images/worstcase.svg

> n queries taking log(n) + n time each is O(n log n)

No, it's O(n^2).

[ Parent | on HN ]
Re:The skyline problem by michaelmior on Tuesday September 02, 2014 @10:29PM (#8261256)
Wow, clearly commenting too late. Of course you're right :)
[ Parent | on HN ]