4
$\begingroup$

While Time Complexity is the measure of how an algorithm scales with respect to input size, Space Complexity on the other hand measures how much the memory scales as input changes.

I see programmers pre-dominantly using these 2 metrics but are there any other generic measures/metrics for comparing the efficiency of 2 or more algorithms?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ This may be on a different level, but one aspect that is not covered by time and space complexity is the parallelizability of algorithms. I'm unsure whether similar clear notations like those you mentioned are also common for this aspect, but it may be a good idea to look for something like that. I'm from practice and there one does benchmarks to get a measure on parallelization scaling, parallelization efficiency and similar quantities. Of course you might try to determine parameters of Amdahl's law or Gustafson's law. $\endgroup$
    – Gregor Michalicek
    Aug 13 at 11:02
  • 2
    $\begingroup$ When it comes to real code and real hardware, it may also be of use to discuss algorithm performance in terms of the roofline model. $\endgroup$
    – Gregor Michalicek
    Aug 13 at 11:05
  • $\begingroup$ @GregorMichalicek: IMO, a parallel version of an algorithm is a different algorithm. I mean both conceptually and concretely. I'd rather speak of the processor efficiency of the parallel algorithm than of "parallelizability". $\endgroup$
    – user16034
    Aug 14 at 6:47
  • 1
    $\begingroup$ Time and space are two resources. You might consider efficiency regarding other kind of resources. For example, the number of disk accesses. $\endgroup$
    – user16034
    Aug 14 at 6:51
  • 1
    $\begingroup$ In distributed systems there is: en.wikipedia.org/wiki/Communication_complexity $\endgroup$
    – cody
    Aug 15 at 20:43

1 Answer 1

Reset to default
6
$\begingroup$

When it comes to the numerical methods used in science and engineering, one important measure is numerical accuracy.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Also described in terms of numerical stability. $\endgroup$
    – user16034
    Aug 14 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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