Re:The true cost of linked lists
by mattarm on Monday June 06, 2022 @11:53AM
(#31642060)
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.
[ Parent
| on HN ]
See also the "galactic" algorithms:
https://en.m.wikipedia.org/wiki/Galactic_algorithm
Re:The true cost of linked lists
by kevin_thibedeau on Monday June 06, 2022 @12:28PM
(#31642506)
Smaller N happens a lot in the real world. Sequential search can beat binary search for sufficiently small N despite being the "worse" choice.