9 ms·

Also like O(N^2) is surprisingly doable even for very big N. Maybe I shouldn't have been surprised, but another problem was N^2 for a pretty big N (100k) with a

by JZL003 4y ago

Also like O(N^2) is surprisingly doable even for very big N. Maybe I shouldn't have been surprised, but another problem was N^2 for a pretty big N (100k) with a dynamic programming. I was worried it would never finish But making a 100k by 100k matrix in julia really isn't so bad (and can use memoization), just rent a big machine on GCP for an hour or two, and it chewed through it fast

kadoban 4y ago
Competitive programming gives you some good intuition on these types of things. N of around 100000 is where you stop looking for O(n^2) algorithms, but the key there is you only have single-digit-seconds for your solution to run. Which is just to say: yeah, machines can chew through _a lot_ of crap, especially if it's not something a user has to wait for and you can do it over-night or something.