5 ms·

But you also spend time on updating cells, so it is not that intuitive.

• LPisGood 1y ago
  I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes. More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.
  • Almondsetat 1y ago
    If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage. If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).
    • deleted 1y ago
      [deleted]
    • bmacho 1y ago
      In other words M <= T.
    • withinboredom 1y ago
      This is pretty easy to refute: > If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.[sic] This is clearly refuted by all software running today. Programs (especially games) clearly use more memory than there are instructions in the program. > If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time). Memory bombs use an incredible amount of memory and do it incredibly quickly.
      • Almondsetat 1y ago
        >Programs (especially games) clearly use more memory than there are instructions in the program. How can you access a piece of memory without issuing an instruction to the CPU? Also, "clearly" is not an argument. >Memory bombs use an incredible amount of memory and do it incredibly quickly. How can you access a piece of memory without issuing an instruction to the CPU? Also "incredibly quickly" is not an argument. Also also, O(n) is incredibly quick.
        • withinboredom 1y ago
          > Also, "clearly" is not an argument. As in your assertion is literally self-evidently false. It is on you to provide a burden of proof here; especially since there are instructions that can load more than a single bit of memory. > How can you access a piece of memory without issuing an instruction to the CPU? Let me rather ask you this: where do the instructions exist that are running? That is right: in memory. However, just because instructions exist in memory doesn’t mean they’re accessed. There is not a relationship between the number of instructions and the amount of memory accessed/used.
          • Almondsetat 1y ago
            This is about time and memory complexity, which is a formal field of computer science. Your replies are about your own vague understanding of computing, which is not the topic here.
            • withinboredom 1y ago
              Yes, but you are asserting the relationship is directly connected -- which is clearly not true. You said that it is O(n) memory and O(n) time, both using n. That means a program containing x bytes can only run for x seconds. This is clearly not true.
              • Almondsetat 1y ago
                >That means a program containing x bytes can only run for x seconds. That is not what it means. Again, if you are not familiar with the notation then all you are doing is slapping your personal ideas about computing to some symbols
  • delusional 1y ago
    This is obviously demonstrably true. A Turing running in O(n) time must halt. The one in O(n) space is free not to.
    • thaumasiotes 1y ago
      Almondsetat's proof seems more obvious. Given O(n) time, you can only use O(n) space, so you're comparing "O(n) space, any amount of time" with "O(n) space, O(n) time", and it turns out you get more resources the first way.
  • qbane 1y ago
    A time-bounded TM is also space bounded, because you need time to write to that many cells. But the other way is not.