← Back to context

Comment by Almondsetat

19 days 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).

9 comments

Almondsetat

Reply
withinboredom  18 days 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  18 days 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  17 days 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.

      4 replies →