> So O(n) could be faster than O(log n) depending on the size of the data structure and interactions with RAM pre-fetch, etc.

This has always been the case. The RAM effects only changed at which point the O(n) stops being faster than the O(log n) solution.