News for hackers. Stuff that matters.
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.
Re:The true cost of linked lists by varajelle on Monday June 06, 2022 @12:19PM (#31642390)
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.
Re:The true cost of linked lists by sitkack on Monday June 06, 2022 @03:10PM (#31644577)
Because in Software Engineering, layout matters. Computing Machines don't care about asymptotic behavior.