Given a system (S) that accepts a tuple of parameters ($\alpha, \beta, \gamma \dots$ etc). These parameters affect the performance of S in a different way. For instance, decreasing $\alpha$ would improve performance of S at some rate, whereas decreasing $\beta$ has a reversed effect. How can one define a performance metric that captures the effects of all parameters in a simple, clear and correct manner.

If the system exists in reality, hence measurements can be taken arbitrarily, what approach one can use to achieve an accurate metric?

I give an example to clarify the question:

Suppose I have a sorting algorithm (A). Performance of A depends on the number of input numbers, precision of the numbers (32, 64, ...) bit, or whether they are partially sorted or not (assuming this can be quantified somehow). Let's limit ourselves to only these 3 factors. If we say A sorts 1000 numbers in 1 millisecond. This doesn't say anything about precision nor entropy of the input. How can we come up with a standard, metric, or unit to describe the performance of A using preferably a single number with a single unit so that they capture all the factors mentioned above.

  • $\begingroup$ I don't understand what you are asking. What do you mean by "define a performance metric"? If you care about the performance of the system, you need to tell us what you mean by the performance of the system. Maybe that's the throughput of the system, or the latency, or something else. It's not clear what that has to do with the parameters, either. Overall, I don't understand what you are asking. Please edit the question to elaborate. Perhaps give an example, tell us what approaches you've considered and why you rejected it, and do whatever you can to explain what you mean. $\endgroup$
    – D.W.
    Jan 9, 2018 at 23:44
  • $\begingroup$ So, you seek a procedure, that given an algorithm, finds an (exact) formula for the running time, given some known data of the input? Or are you satisfied with only the asymptotic behavior, but for a more specified input model? I doubt there is a general procedure to do this, but I believe Knuth's 'the art of computer programming' has a large emphasis on exact running times (which is rather difficult, in general). $\endgroup$
    – Discrete lizard
    Jan 10, 2018 at 12:49
  • $\begingroup$ That would be amazing if such a procedure exists. I will check Knuth's TACP. $\endgroup$
    – caesar
    Jan 10, 2018 at 14:07


Your Answer

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

Browse other questions tagged or ask your own question.