Unconscious Algorithms

https://droctothorpe.github.io/posts/2020/12/unconscious-algorithms/

by droctothorpe • 6 years ago

14 4 6 years ago

droctothorpe.github.io

scaramanga2• 6 years ago

The time and space complexity are both O(n)

Actually the worst case time complexity is O(n * m). To see why, imagine searching for a big string of the form "aaa...aaax" in the much bigger string of the form "aaa...aaax".

The analysis case for average time is more tricky. You could intuitively think that it, too, should include an "m" term, right? But if strings are uniformly random then the probability of finding your way in to the n'th character of the needle from any given start position decreases geometrically (1, 1/256, 1/65536, ...). Since the sum of any such geometric series is a constant[0], we end up with O(n) * O(1) so it's just O(n).

[0]. https://en.wikipedia.org/wiki/Geometric_series#Sum

droctothorpe• 6 years ago

I really appreciate the nuanced analysis! Thanks for the input!

scaramanga2• 6 years ago

Any time! Keep writing!

coolgeek• 6 years ago

I don't know if Pinker attributes this (or if he independently came up with the observation), but the quote relates to Moravec's Paradox

https://en.wikipedia.org/wiki/Moravec%27s_paradox

Unconscious Algorithms

Related Stories