Re:14,000x Speedup (2015)
by leeter on Tuesday October 13, 2020 @12:13PM
(#24766937)
People forget that Big O is only part of the story, they also need to consider Little o and average runtime. Just because something is n^2 or worse asymptotically doesn't mean the average runtime will be that bad. There are many cases where the average runtime is closer to Little o almost all the time.
[ Parent
| on HN ]
Re:14,000x Speedup (2015)
by zimpenfish on Tuesday October 13, 2020 @06:49PM
(#24771210)
> they also need to consider Little o and average runtime.
Frequency of run is also important - a batch job that takes 5 hours that only runs once a month? Is it worth optimising that?
Average is useful but is Little o relevant outside of very low latency things like games? If the input is small it will run fast for any solution anyway.