Besides brute force decryption, does anyone have some good examples of O(2^N) al... | Hacker News

Hacker News new | past | comments | ask | show | jobs | submit

login

hypnocode on Aug 22, 2012 | parent | context | favorite | on: A Beginner’s Guide to Big O Notation

Besides brute force decryption, does anyone have some good examples of O(2^N) algorithms?

Also: http://www.kurzweilai.net/software-progress-beats-moores-law Algorithmic improvement account for more of the acceleration in computing power than physical factors, such as transistor density.

tsahyt on Aug 22, 2012 [–]

SAT for instance has only been solved with O(2^n) algorithms so far. The tricky thing here is that we don't quite know whether it could be done any quicker (google up P=NP for a more detailed description).

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