To me, all this article has show is that depending on the size of a data structure, you will need slower and slower memory. We already know that. The article shows that within the bounds of a particular type of memory the access time is mostly constant, which is exactly what O(1) means.