3 ms·
Something that the author seems to be missing is that traditional complexity analysis (with mathematical proofs etc) is done for Turing Machines which have one-
by solarexplorer 10y ago
Something that the author seems to be missing is that traditional complexity analysis (with mathematical proofs etc) is done for Turing Machines which have one-dimensional memory (an abstract tape), and reachable memory is linear with time. Current microchips are two-dimensional, so reachable memory increases square with time. If we had three dimensional memory (stacked chips?), then reachable memory would increase cube with time.
It all depends on what kind of machine you are talking about...
- jimbokun 10y agoHe addresses using the third dimension in detail in part II: http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-part-ii http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-p...
- skykooler 10y agoAs he mentions, three-dimensional memory is impractical right now due to cooling concerns.
- lorenzhs 10y agoWhat? No! (Sequential) algorithms are usually analysed in the Random Access Machine Model (RAM model). That's a machine that can access any memory location in constant time, and perform arithmetic operations in constant time. See https://en.wikipedia.org/wiki/Random-access_machine https://en.wikipedia.org/wiki/Random-access_machine A Turing machine can only go left or right one cell in each step, so e.g. comparing two strings for equality takes O(n²) time as you have to go character by character, moving the head over a suffix of the first word and a prefix of the second word for every character.