[mathattack]

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]

That is yet another section of the article, the thousand years clearly reference the edit distance, which is quadratic.