3 ms·
I think that makes sense only for smaller n. At some point your "sufficiently large constant" will need to essentially be computed from the "worse big-O" algor
by mattarm 4y ago
I think that makes sense only for smaller n. At some point your "sufficiently large constant" will need to essentially be computed from the "worse big-O" algorithm to slow the "better big-O" algorithm down enough. E.g. making an O(N) as slow as an O(N^2) algorithm would require a sufficiently large constant roughly equivalent to N^2, at which point you really just have turned the O(N) into O(N^2) in practice.
- varajelle 4y agoSee also the "galactic" algorithms: https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm
- kevin_thibedeau 4y agoSmaller N happens a lot in the real world. Sequential search can beat binary search for sufficiently small N despite being the "worse" choice.
- sitkack 4y agoBecause in Software Engineering, layout matters. Computing Machines don't care about asymptotic behavior.