2 ms·
1,000 years? Really? Isn't it more likely that somebody misquoted "slow, like a half an hour" as "slow, like a THOUSAND YEARS"?
by daveloyall 11y ago
1,000 years? Really?
Isn't it more likely that somebody misquoted "slow, like a half an hour" as "slow, like a THOUSAND YEARS"?
- mmarx 11y ago>>> 1000 / ((1024. ** 6) / 3e9 / 86400 / 365) 82.0593593076069 The algorithm is quadratic in the input size. For a Gigabyte of data, that's 1024^6 operations. Dividing that by 3 * 10^9 operations/second (assuming a 3GHz CPU), 86400 (the number of seconds in a day), and 365 (the number of days in a year), we obtain the runtime (in years) assuming that comparing a single byte takes exactly one operation. Dividing 1000 by that number, we get ~82 operations to compare a single byte, and that doesn't look unreasonable.
- mathattack 11y agoThey'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.