3 ms·
They're quoting exponential (2^N), not quadratic (N^2) time. If on some machine a quadratic-time algorithm took, say, a hundredth of a second to process 100 el
by mathattack 11y ago
They're quoting exponential (2^N), not quadratic (N^2) time.
If on some machine a quadratic-time algorithm took, say, a hundredth of a second to process 100 elements, an exponential-time algorithm would take about 100 quintillion years.
- mmarx 11y agoThat is yet another section of the article, the thousand years clearly reference the edit distance, which is quadratic.