The Myth of Ram - part I

http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i

• O(sqrt(N)) instead of O(1) for accessing RAM => O(N*sqrt(N)) for going through linked list
• simple program accessing linked list. Accessing element is not O(1) (plot) (1ns -> 1 microsec)
• several levels of caching -> O(sqrt(N))