The fact that suffix trees/suffix arrays can be built in O(n) is IMO the most su...

		dinobones on July 22, 2022 \| parent \| context \| favorite \| on: Ask HN: What are some cool but obscure data struct... The fact that suffix trees/suffix arrays can be built in O(n) is IMO the most surprising and "magical" result in computer science. To me, more surprising than median of medians/quick select. There might be more "magical"/surprising things that are obscure and I am unaware of, but to me, this is it. :)

what about randomized O(n) minimum spanning trees?