News for hackers. Stuff that matters.

A comment on Ask HN: What are some cool but obscure data structures you know about?. Parent comment

Re:Ask HN: What are some cool but obscure data structures yo... by umanwizard on Thursday July 21, 2022 @11:41PM (#32188243)
Do we mean different things by "merge join" and "nested loop join" ? For me "merge join" is O(n) (but requires the data to be sorted by key) whereas "nested loop join" is O(n^2).
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by mountainreason on Thursday July 21, 2022 @11:52PM (#32188321)
Wouldn't you at least be looking at nlog(n) for the sort in the merge join?
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by umanwizard on Thursday July 21, 2022 @11:58PM (#32188350)
Yes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by mountainreason on Friday July 22, 2022 @09:40AM (#32191770)
Yeah. I know. Why would the data already be sorted?
[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by umanwizard on Friday July 22, 2022 @10:39AM (#32192327)
In a database you might have already built an index on that data.
[ Parent | on HN ]