Re:Decreasing the Number of Memory Accesses 1/2
by mrguyorama on Friday March 31, 2023 @02:54PM
(#35391625)
My algorithms class discussed the importance of not forgetting the constants. We talked about an algorithm for recursively taking averages of a list of numbers (or whatever that's not important) that was O(n^2) but only in worst case, while there was a version that is guaranteed O(nlogn) or something but the constant factor was 27. This meant the growth only mattered in extreme cases.
[ Parent
| on HN ]
Re:Decreasing the Number of Memory Accesses 1/2
by karmakaze on Monday April 03, 2023 @09:44AM
(#35423450)
That math doesn't seem to check out. Say with base-2 log and a 27 factor difference, for 1000 it would be 1000^2 = 1,000,000 vs 27 * 1000 x log 1000 = 270,000. I wouldn't call n=1000 an extreme case for most problems. Just because practical counterexamples exist, don't think that it applies to your problem unless demonstratably so, an then still worry about N being larger than originally designed for.