3
$\begingroup$

I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some resources where I can learn to calculate the complexity of an algorithm?

Secondly, is there some software that calculates the space and time complexity for an algorithm? I have seen that cyclomatic complexity can be calculated by software.

$\endgroup$

migrated from cstheory.stackexchange.com Jun 5 '13 at 18:34

This question came from our site for theoretical computer scientists and researchers in related fields.

7
$\begingroup$

Depending on your background, the CLRS book is a solid introduction. I think in the very first chapter, they walk you through of how to analyze a simple algorithm in terms of both correctness (showing the algorithm really solves the problem) and complexity (how many steps the algorithm performs). There are lots of other books out there some other people might prefer more.

In general, there is no software that does this for you. Coming up with right invariants etc. is somewhat of an art requiring insight and experience. Read more about complexity theory, and you'll discover some inherit impossibilities and problems related to automating such analysis.

$\endgroup$
  • $\begingroup$ In general, there is no software that does this for you. — In fact, the undecidability of the halting problem guarantees that no such software can exist, even in principle. $\endgroup$ – JeffE Jun 6 '13 at 0:25
  • $\begingroup$ @JeffE Yes, that's what I was referring to with the inherit impossibilities. $\endgroup$ – Juho Jun 6 '13 at 1:16
  • 2
    $\begingroup$ Over at cstheory, there is a proof that runtime bounds in P are not decidable in this question. $\endgroup$ – adrianN Jun 6 '13 at 8:37
  • $\begingroup$ Apart from not being decidable in general, some algorithms have a runtime that is very, very difficult to figure out. $\endgroup$ – gnasher729 Sep 18 '18 at 7:43
-1
$\begingroup$

It is entirely possible with simple curve fitting exercises, which could be automated. Bearing in mind Juho's answer, some estimate must be better than no estimate whatsoever. And some estimate is certainly possible for many algorithms, especially those that don't have many major decision branches and always halt such as cryptographic ones, compression, etc.

  1. Code your algorithm.

  2. Provide a test framework around it that can feed in different values of $n$.

  3. Run the algorithm and time it's execution for each $n$.

  4. There are only a few generic complexities to choose from if you are not too concerned with a perfect analysis. A good example set is simply listed on the relevant Big $O$ Wikipedia page. And any analysis must be better than none.

  5. Iterate through the generic $O$ formulae, curve fitting and choose the best fit using your favourite fitting technique. Some experience and black magic may be useful in pruning the set.

This may not be academic computer science, but that's how the military, economics, engineering and politics works in this world. Monte Carlo simulation is exactly this type of analysis. The following simple example from Wikipedia is another:-

np

We see that the run time is approximated to $O((log(n)^2)$ which is polylogarithmic time. The specificity of the example is important. It's entirely possible that this approximation would be impossible to compute algebraically due to the overwhelmingly complex architecture of a Pentium 3 processor.

Reiterating, something is better than nothing and this example proves that automated complexity analysis is not only possible, but can be rather simple.

$\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.