The myth of RAM, and of O(n), and of NNO

[bytebuster]

Чудове чтиво про те, що навіть доступ до масиву займає не O(1), а O(√N).
На картинці показаний доступ до RAM, про який вважається, що він займає O(1). Якби доступ був константним, то і графік був би горизонтальним.

Originally posted by juan_gandhi at the myth of RAM, and of O(n), and of NNO

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

see also http://philosophy.stackexchange.com/questions/37665/are-there-simpler-kinds-of-arithmetic-that-are-decidable

and I wonder when we start using linear logic IRL