Hacker News new | ask | show | jobs
by jltsiren 781 days ago
As the amount of data grows, exponents that used to be small become large.

In many applications, the data grows at least as quickly as computer performance. If the fastest known algorithm is superlinear, today's computers take longer to solve today's problems than yesterday's computers solving yesterday's problems. While O(n^2) time algorithms used to be pretty fast in the 80s, today they are often unusable.

1 comments

I completely agree with you. My point was that the P vs NP distinction matters in practice, but of course also the subquadratic vs quadratic time distinction matters a lot.