Wouldn't you at least be looking at nlog(n) for the sort in the merge join? | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		mountainreason on July 22, 2022 \| parent \| context \| favorite \| on: Ask HN: What are some cool but obscure data struct... Wouldn't you at least be looking at nlog(n) for the sort in the merge join?

umanwizard on July 22, 2022 [–]

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.

mountainreason on July 22, 2022 | [–]

Yeah. I know. Why would the data already be sorted?

umanwizard on July 22, 2022 | | [–]

In a database you might have already built an index on that data.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact