The "n" the author is really talking about may be the depth of the cache hierarchy.
The "n" the author is really talking about may be the depth of the cache hierarchy.
[1] http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-pa...
If this has nothing to do with Big-O then Big-O is a useless concept and should be abandoned. You may be interested in measuring the number of CPU instructions it takes to traverse a linked list in which case O(N) is accurate.
Personally I care about how much wall-clock time it takes in which case a linked list is very much not O(N) and the larger the list the further away from O(N) it becomes. There is a rather large delta between a 10K and a 100MB linked list. You can go test this for yourself right now.
> Random access in memory is still in O(1)
No it isn't. Random access only looks like O(1) at certain plateaus, like size of L1, size of L2, size of L3, size of RAM on the local NUMA node, size of RAM on neighboring NUMA nodes, size of RAM on distant NUMA nodes, size of SSD, size of HDD, size of NAS locally connected, size of NAS distantly connected, size of cloud storage.
Constants can matter in Big-O, especially if they are very large. Compared to the number of instructions 3Ghz CPU must execute to do a hash lookup, accessing RAM has a relatively large constant factor and execution time can be massively impacted by sub-optimal RAM access patterns.
EDIT: I mean, consider that the entire basis for Big-O notation assumes that every "operation" are always equal. Adding is always constant. Big-O is very hand wavey and claiming the constants matter is to invent an entirely new notation.
Your other questions are all best answered by: Big-O notation is not the right tool if you want to make predictions about wall-clock time. I don't think I need to justify why someone interested in wall-clock time would be very interested in the constant factors involved - the difference between n and 20n is a factor of twenty, and whether a program takes half a second or ten does make quite the difference.
But asymptotically, they're the same. Someone who is interested in the asymptotic behaviour wants to know how fast the function grows - is it linear? linearithmic? quadratic? cubic? exponential? (with which base - 1.1^n, 2^n, 10^n?). For them, a constant factor isn't interesting.
Of course, neither extreme is particularly helpful when trying to compare algorithms in practice. Modelling the hardware extensively and including all the little constant factors is exceedingly tedious, even if you can actually get all the information required to do so. Pure asymptotics also don't help much if they hide huge constant factors. That's why Algorithm Engineering is a thing (and a very good thing!). Basically, it tries to bridge the gap between algorithms that theorists like, and those that practitioners use. To that end, design, analysis, implementation, and experimentation must form a circle and influence each other. Wikipedia probably does a better job of explaining it, though.