I don't think he means big-O notation as a theoretical model... Processors are not the same as they were when they were single core machines. The entirety of co

I don't think he means big-O notation as a theoretical model... Processors are not the same as they were when they were single core machines. The entirety of computing and thinking about problem solving has become different than it was before 2005 because of multicore processor architecture. Projects like parallela make this obvious. Programmers in general don't understand how much this makes things that weren't a big deal 10 years ago a huge deal now. And stuff with threading is not even the tip of it. Threading is trivial compared to real parallelism. Our model of computation is different than it is now, and will continue to diverge until everybody starts thinking with parallel as a first priority. That's the most convincing argument the OP makes about why linked lists are bad. In parallel computing, they are definitely hard/bad.