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

In the real world, we care about runtime as much as, if not more than, computational complexity.



Definitely more. There are lots of things that might be more optimal in terms of raw complexity but end up having abysmal performance due to things like cache locality. Anything with pointer chasing usually kills performance.


for example, matrix multiplication has all sorts of algorithms with exponent significantly less than 3, but they are nearly all curiosities. In practice, the straightforward N^3 algo is used nearly everywhere


I had a long discussion with Rob Pike once that ended with me saying "you know, I don't think people actually use Strassen on supercomputers" (we were discussing how somebody had managed to show an N*2.37 algorithm or something like that and "it was a new world's record").


nit: ^, not *. ** for Python, but never *


Unfortunately Hacker News editor converts double-asterisk to single which is what caused the problem.

I never use ^ for "to the power of" due to its use in C for bitwise OR.




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

Search: