6 ms·
It's a nice theoretical result. In practice there are some quirks though: - I assume this is worst case complexity. While this is useful, maybe the average tim
by leni536 11y ago
It's a nice theoretical result. In practice there are some quirks though:
- I assume this is worst case complexity. While this is useful, maybe the average time can be much lower for certain data (like the genome).
- I assume the theorem doesn't restrict the input strings in any way. If you put restrictions on the input then there could be a faster algorithm than the general one. I don't know if this can be applied to the genome though.
- People are interested in the constant factor too.
- codeflo 11y agoAlso, a fast approximation with a good error bound might be good enough for many applications in biology.
- Asbostos 11y agoAbsolutely. This is surely more theoretical than practical. Solving a linear system of equations has cubic complexity but we still routinely solve systems with millions of equations. Billions are probably being done too. We just take advantages of special features that allow us to do things faster than the worst case - such as having a sparse matrix.