2
$\begingroup$

We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space. However, I feel this does not capture the full story.

Say we have a process that looks like this. Assume memory allocation is O(1) time complexity for simplicity.

process(n):
  mem = allocate(n) 
  for 0 to n:
    ... do O(1) stuff
  end
  free(mem)
  end

The above process takes O(n) time and O(n) space.

Here's another process that takes O(n) time and O(n) space.

process(n):
  for 0 to n:
    ... do O(1) stuff
  end
  mem = allocate(n)
  ... do O(1) stuff
  free(mem)

In the both processes you're using O(n) space. In the first one you're using the space over the course of the entire process. In the second, you're using it only at the very end. Is there a way to formalize the difference?

$\endgroup$
4
$\begingroup$

Sure. Of course, you are absolutely right, that time complexity and space complexity don't capture the whole story. No one metric is likely to.

There are many ways one could plausibly distinguish between those two programs. For instance, one could ask about average space usage (averaged over the lifetime of the program). These metrics might be harder to use, but might be more relevant in some situations. Only you can know what you want to optimize, so you only you can determine which metric is most suitable for your particular situation. You might find that asymptotic analysis is not the best tool for the job and instead you want to measure space usage on a real-world benchmark/workload. That is also reasonable.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.