3 ms·

> If I take an O(n^2) algorithm and I modify it using an "upper triangle" optimization, I cut the time in half, but it's still O(n^2). That is why the Landau s

by q-big 4y ago

> If I take an O(n^2) algorithm and I modify it using an "upper triangle" optimization, I cut the time in half, but it's still O(n^2). That is why the Landau symbols are a strong simplification to get an estimate how fast the runtime grows in the worst case as n -> ∞. When two algorithms are in the same Θ(...) class, you must also consider the constant that the Landau symbol "hides" to get a more fine-grade measure of the algorithm's worst-case performance (even if two algorithms are not in the same in the same Θ(...) class, such a more fine-grained measure does make sense because "for sufficiently large n" does not imply "for the n that are relevant for the application").

hinkley 4y ago
In the old days it would have been pretty typical for me to build an application by gluing a bunch of independent libraries together, in which case any slowdowns they might experience are purely additive, and so would not effect the complexity (although linear slowdowns are still not just annoying but potential company killers, and so what an academic tells you to worry about doesn't mean all that much in the crucible of production). But that hasn't been the case for decades now, and so you can't think of it that way. All of my libraries are themselves gluing together as many libraries as I'm gluing together, and so I can include 20 libraries directly in a large application and end up with 300. There are no guarantees that these effects will be cumulative instead of multiplicative. Assuming they are is not dangerous, it's negligent. If you can't assume a lower bound, or an upper bound, then you don't know Ω or O unless you code review the entire code base, which almost nobody does. Best you're going to do on that is empiricism, which is the bare minimum amount of responsibility (which is still skipped by many people). If you don't know Ω and you don't know O, then any claims you're making about Θ are bullshit.

by q-big 4y ago

hinkley 4y ago

In the old days it would have been pretty typical for me to build an application by gluing a bunch of independent libraries together, in which case any slowdowns they might experience are purely additive, and so would not effect the complexity (although linear slowdowns are still not just annoying but potential company killers, and so what an academic tells you to worry about doesn't mean all that much in the crucible of production). But that hasn't been the case for decades now, and so you can't think of it that way. All of my libraries are themselves gluing together as many libraries as I'm gluing together, and so I can include 20 libraries directly in a large application and end up with 300. There are no guarantees that these effects will be cumulative instead of multiplicative. Assuming they are is not dangerous, it's negligent. If you can't assume a lower bound, or an upper bound, then you don't know Ω or O unless you code review the entire code base, which almost nobody does. Best you're going to do on that is empiricism, which is the bare minimum amount of responsibility (which is still skipped by many people). If you don't know Ω and you don't know O, then any claims you're making about Θ are bullshit.