I think there are already tags for complexity-theory and time-complexity. The descriptions are similar. What benefit does runtime-analysis bring to the table?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ time-complexity is a complexity theory concept, it is about a computational problems's required time to solve independent of what algorithm we are using, runtime-analysis seem to be about analyzing the runtime of a particular algorithm and is an algorithmic concept. $\endgroup$– KavehApr 24, 2012 at 16:07
-
$\begingroup$ @Kaveh That seems to conflate the ideas of complexity and complexity class. If what you're arguing is that runtime-analysis is a kind of application of time-complexity, OK; but do we need separate tags for theories and how they're applied? $\endgroup$– Patrick87Apr 24, 2012 at 16:13
-
$\begingroup$ time-complexity+algorithms might give a similar meaning to algorithm-analysis, I think people will interpret the pair as asking for an upper-bound on a problem (no algorithms mentioned explicitly) and the second one as asking for analyzing a particular algorithm (which doesn't need to about any problem). How important is this distinction? not much for me personally but it might be for others, e.g. some might want to ignore questions about analyzing people's algorithms while still interested in upperbound questions, or vice versa. $\endgroup$– KavehApr 24, 2012 at 16:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Time complexity is about asymptotic bounds on worst, best or average case resource consumption needed to solve problems.
Runtime analysis deals with explicit runtimes of a given algorithm on specific inputs (and functions thereof).
Asymptic best/worst/average case behaviour of a given algorithm falls somewhere in between.
Algorithm analysis is way broader than runtime analysis, as it also subsumes space and energy consumption, parallelity, correctness and every other property an algorithm can have.
As we have not used runtime-analysis a lot I guess we can drop it in favor of algorithm-analysis; most will want to analyse runtimes, anyway, so we might need tags to mark other measures but certainly not runtime.
-
$\begingroup$ Is this distinction between "time complexity" and "runtime analysis" common? Is there some (authoritative?) reference that draws this distinction? While I agree that "runtime" does have a somewhat stronger connotation of an application to a particular algorithm, it was never my impression that this was institutionalized. In any event, time complexity and runtime analysis must be very closely related... $\endgroup$ Apr 24, 2012 at 20:47
-
$\begingroup$ I suppose it's the presence of "run"... since algorithms, per se, don't run... only implementations do. $\endgroup$ Apr 24, 2012 at 20:48
-
$\begingroup$ @Patrick87: Every formal treatment of complexity I have seen starts with defining runtime on inputs $T_A(x)$ and only then worst-case runtime $T_A(n) = \max_{x \in I_n} T_A(x)$ whose asymtotics are then considered as "complexity". So, runtime and "time complexity" are separate, if related notions. Due to the level of abstraction, complexity analysis most often does not yield any useful information about actual runtimes. What Knuth does in TAoCP, for instance, is (archetypical) runtime analysis. $\endgroup$– Raphael ModApr 24, 2012 at 21:20
-
$\begingroup$ So there are lots of references which explicitly draw this distinction between runtime (as in a specific function, not an asymptotic case bound) and time complexity (which only refers to the results of asymptotic analysis applied to case bounds of functions obtained from runtime analysis)? Are any of these references online? Alternatively, does e.g. Knuth say that what he is doing is "runtime analysis, not time complexity" or similar? $\endgroup$ Apr 24, 2012 at 21:31
-
$\begingroup$ @Patrick87: I don't know about "lots of references"; I know that Cormen et al., for instance, do make this separation. The Wikipedia article is less clear, sadly, but it does mention the separate concepts. $\endgroup$– Raphael ModMay 14, 2012 at 16:03