1
$\begingroup$

Seriously why do we consider how the computation time time increase with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,memory usage etc?Because all of these facts are depends on the hardware and programming language we use in that moment and order growth is only depends on inputs?

$\endgroup$

marked as duplicate by David Richerby, Evil, Discrete lizard, Yuval Filmus algorithms Jul 7 '18 at 21:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ We can analyze the asymptotic running time of an algorithm without ever programming it. $\endgroup$ – Yuval Filmus Jul 7 '18 at 16:10
  • $\begingroup$ There is two separate topic to be discussed here. 1) why asymptotic w.r.t. input size 2) why time. (as you see memory --- one of the thing OP suggested as alternative --- is also popularly measurable via asymptotic) $\endgroup$ – Apiwat Chantawibul Jul 7 '18 at 16:25
  • $\begingroup$ In fact, basically an exact duplicate, but the above is an automatically generated comment. $\endgroup$ – David Richerby Jul 7 '18 at 17:59
2
$\begingroup$

I think the key point in time complexity analysis is it can give us a metric to measure the time independent of any hardware or software dependency directly.

Hence, we can talk about the time complexity based on inputs and outputs of the problem without considering more sophisticated or even complex cases by mentioning that we are talking about the hardware or software specifications.

However, hardware usage is mentioned in some real applications too, somewhere the time complexity can't distinguish the solutions in its abstract asymptotic definition. These kind of analysis are common in AI algorithms which have the same time complexity but have some real differences in real applications and hardware usage. For example, in real applications "Quick Sort" is better than "Merge Sort" because we have a large constant factor in "Merge Sort" time complexity, however, on the paper, in time complexity, "Merge Sort" is better than "Quick Sort" in worst cases.

In sum, time complexity base on the growth can be proper to compare algorithms independent of any hardware or software specifications, although hardware usage in real applications makes sense more!

$\endgroup$

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