Comment by 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.
>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.
> 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.
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.
3 replies →