8 ms·
I mean nobody is stopping me from writing an exponential time algorithm.
by nnoremap2 2y ago
I mean nobody is stopping me from writing an exponential time algorithm.
- Dylan16807 2y agoSure? If you're slow on purpose that doesn't affect the upper bound set by the "obvious" method.
- jakeinspace 2y agoI think they’re replying to the claimed upper bound of n^3. I’m not actually sure what that means.
- demurgos 2y agosee schoolbook algorithm for the n^3 bound: https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication https://en.wikipedia.org/wiki/Computational_complexity_of_ma... It comes from directly applying the definition of matrix multiplication on a square matrix.
- Dylan16807 2y agoI'm not sure how to phrase this better than saying it's the bound set by the obvious method. Are you familiar with the obvious method of multiplying a matrix? It's n operations for each cell, and you have n^2 cells. Being worse on purpose is always possible, but it doesn't change that bound. It's the "obvious" upper bound, not the "how did you even get here without noticing the obvious method" upper bound.
- adrianN 2y agoKnowing an upper bound means you know that the best solution for the problem takes at most that much work. It does not mean that you can’t find worse solutions.