10
$\begingroup$

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)?

I googled "Automatic algorithm analysis" which gave me this but it is too mathy. I just want a simple example in psuedocode that I can understand. Might be too specific, but I thought it was worth a shot.

Improve this question
$\endgroup$
3
  • $\begingroup$ I fail to see how stressing between "any" and "an" clarifies what you really are after. If some decision procedure is bound to a particular algorithm B, then there is no real input and the answer is always the same. I think what you want to ask is if 'any algorithm within some class of algorithms' where the class is bound/known. (edit: this has been pointed out my mhum's comment as well). $\endgroup$ – Nicholas Mancuso Dec 5 '14 at 18:43
  • 2
    $\begingroup$ The ambiguity in your use of "an" and "any" is exactly why quantifiers were invented. $\endgroup$ – Nate Eldredge Dec 6 '14 at 5:32
  • 2
    $\begingroup$ I edited the question to focus on the relevant parts. Note how I use exactly zero mathematics to express the problem accurately (as far as you specified your question until now) and succinctly. Now, the question is still ill-posed: of course there are such algorithms. For example, there's a simple algorithm that analyses all algorithms from the (very relevant) class of algorithms that run in time $\Theta(n \log n)$. Hence you clearly need to put some restrictions on the sets of inputs. (Note that there might not be "a simple example in psuedocode that I can understand".) $\endgroup$ – Raphael♦ Dec 6 '14 at 8:25
12
$\begingroup$

The COSTA tool does just this, although it fails in many cases, as you can imagine, due to computability problems. There are many papers about this; Cost Analysis of Java Bytecode by E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini is a good starting point.

The approach taken is to infer a run-time recurrence from the Javabyte code, the convert this to a closed form. The tool also compute space usage bounds.

Improve this answer
$\endgroup$
1
  • 8
    $\begingroup$ @Nathvi I can understand you are irritated by some comments, which I agree were not really necessary, but you should also be careful not to use the term "pedantic drivel" for the work of very reputable scientists (and incidentally my answer). You are entitled not to like mathematics, but you are unlikely to get very far without it, and gratuitous derogatory words help no one. $\endgroup$ – babou Dec 5 '14 at 10:02
12
$\begingroup$

No algorithm can decide whether a given algorithm ever halts or not, so in particular no algorithm can tightly analyze the complexity of a given algorithm.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ My question isn't regarding an arbitrary inputted algorithm, which if it was, then your answer would be correct, due to the halting problem. You would be correct if my question was worded: "Is there an algorithm A that takes in any algorithm B, and then outputs the time complexity of algorithm B?" $\endgroup$ – Nathvi Dec 5 '14 at 1:42
  • 6
    $\begingroup$ If the algorithm B is fixed, then sure there's an algorithm A. It suffices to have an algorithm that does nothing but print "O(n)" or whatever complexity measure corresponds to B. If there is only one possible input to algorithm A, then we only need one output. $\endgroup$ – mhum Dec 5 '14 at 2:07
  • 5
    $\begingroup$ @Nathvi it was also not clear to me - I also understood the question as "is there an algorithm for finding the complexity of any other algorithm", and I still don't understand your real question. If you're into counting upvotes, apparently >2 people interpreted it that way. In case of confusion, it really is a good idea to edit your question, otherwise only people who read this conversation (rather than everybody who reads the question) will understand what you're asking and give good answers. Looks like you felt D.W.'s response was hostile - FWIW, I don't think it was intended to be.. $\endgroup$ – jkff Dec 5 '14 at 5:44
  • 6
    $\begingroup$ @ignis The answer may be incomplete but the sentence that Yuval wrote is absolutely correct. And the halting problem is not some exotic side case: it's the very essence of computation. $\endgroup$ – David Richerby Dec 5 '14 at 11:20
  • 3
    $\begingroup$ @nikie That's doesn't help as far as this question goes; runtime bounds are undecidable even on the set of all always terminating algorithms. $\endgroup$ – Raphael♦ Dec 6 '14 at 8:32
9
$\begingroup$

I know one approach to (semi-)automated average case analysis, namely MaLiJAn¹. It closely resembles the kind of analysis Knuth uses in TAoCP. The core idea is to

  • model the program (flow) as Markov Chain,
  • train its transition probabilities for some fixed input sizes $n$ by counting a set of program runs (which yields maximum likelihood estimators),
  • extrapolate to probility functions in $n$ and
  • use computer algebra to derive the average cost (w.r.t. these functions).

Note that only additive cost measures (e.g. comparisons, "time") work and only the expected value is accurate (assuming perfect probability functions), higher moments can not be derived.

All steps but the extrapolation are rigorous [2] and the method has been demonstrated to reproduce well-known results with high precision -- given suitable random sample inputs, of course. While there is no proof or even approximation guarantee on the results (the extrapolation step is, so far, purely heuristic) the results obtained with the tool serve well to experiment with hard to analyse algorithms and formulate hypotheses [3,4].

  1. Full disclosure: I'm was a member of this research group and had been involved in the development of the tool.
  2. Maximum Likelihood Analysis of Algorithms and Data Structures by U. Laube and M. Nebel (2010) [preprint]
  3. Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al (2012) [preprint]
  4. Maximum Likelihood Analysis of the Ford–Fulkerson Method on Special Graphs by U. Laube und M. Nebel (2015) [preprint]
Improve this answer
$\endgroup$
3
  • $\begingroup$ Do these techniques come with an estimation on the precision of the average case analysis? $\endgroup$ – Martin Berger Feb 16 '15 at 9:15
  • $\begingroup$ @MartinBerger Unfortunately, no. We have some ideas about that but nothing solidified let alone implemented yet. Note that it is easy to fool any method that checks only finitely many input sizes, so there is little hope in general. With assumptions on the runtime functions and/or data sets, something may be possible. The tool should at least be able to say "need more data". $\endgroup$ – Raphael♦ Feb 16 '15 at 9:17
  • $\begingroup$ That's interesting. I hope you get around doing this additional work. $\endgroup$ – Martin Berger Feb 16 '15 at 9:54
8
$\begingroup$

Of course, as noted by Yuval Filmus, one should not expect a general solution to such problems. But as is usually the case, solutions can be found for interesting subsets of the general case.

I am in no way expert, or even significantly knowledgeable in this area, by I happen to know of some work of the kind. It concerns automatic average complexity analysis, and the work was done by Philippe Flajolet and his colleagues.

From what I understood when it was explained to me, the authors designed a small language (nothing Turing complete as you might expect, but significant enough) so that any algorithm written within the constraint of that language could have its average complexity analyzed automatically.The system was called at the time Lambda-Upsilon-Omega, i.e. $\lambda\acute\upsilon\omega$ (I unbind).

One paper I found on the web is a 1990 paper: Automatic average-case analysis of algorithms by Philippe Flajolet, Paul Zimmermann, and Bruno Salvy.

I would expect that later papers have extended this work, but I do not really know. The work was quite heavily cited, and searching the web for it should yield more recent work on the same topic.

Now, I am afraid that the work of Flajolet and his colleagues was very mathematical, and I would not expect much easy reading.

Improve this answer
$\endgroup$

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.