Re:The true cost of linked lists
by bo1024 on Monday June 06, 2022 @11:41AM
(#31641897)
At the extreme ends, there are two kinds of slow computations.
1. A small computation that you perform many, many times.
2. A very, very large computation.
For #2, big-O can still generally tell most of the story. (Example: 100 insertions in the middle of a list with a billion elements.) For #1, big-O almost irrelevant, and benchmarking is key. (Example: a billion insertions into the middle of length-100 lists.) So knowing which situation you're in is important.
1. A small computation that you perform many, many times.
2. A very, very large computation.
For #2, big-O can still generally tell most of the story. (Example: 100 insertions in the middle of a list with a billion elements.) For #1, big-O almost irrelevant, and benchmarking is key. (Example: a billion insertions into the middle of length-100 lists.) So knowing which situation you're in is important.