0

Possible Duplicates:
Program/algorithm to find the time complexity of any given program.
Programmatically obtaining Big-O efficiency of code

Hi, i am eager to develop a function(say computeComplexity()) which can determine the time complexity and space complexity of any algorithm(say bubbleSort()).

Usage of computeComplexity() function can be as below.

void bubbleSort()
{
     computeComplexity();//Start monitoring memory consumption and time spent.
     ....
     .... //Sorting algorithm goes here
     ....
     computeComplexity();//Display time complexity and space complexity
}

Output would look like

Algorithm ran : Bubble sort

Time complexity: O(n^2)

Space complexity: O(n^2)

I am yet to try any approach for this.

I thought, its better to check with experts here first.

Community
  • 1
  • 1
bjskishore123
  • 6,144
  • 9
  • 44
  • 66
  • ... by time and space complexity, I assume you mean [Asymptotically](http://en.wikipedia.org/wiki/Asymptotic_analysis)? In which case, I can see no way to do it with a simple start/stop idea like you have here - you'd actually have the parse the code to look for loops (time complexity), variables created during loops (space complexity), etc. Calculating space/time complexity on code would be mostly an exercise in parsing many different types of code into a known basic pseudo-code... at least, the parsing would take a good chunk of the effort. – Stephen Aug 31 '10 at 13:37
  • 11
    This would be equivalent to deciding the [Halting problem](http://en.wikipedia.org/wiki/Halting_problem). – Bill the Lizard Aug 31 '10 at 13:39
  • 2
    This is a duplicate of http://StackOverflow.Com/questions/1461168/ and http://StackOverflow.Com/questions/480775/ (and probably others as well). – Jörg W Mittag Aug 31 '10 at 13:39
  • As a summary, here's a quick sketch: determining the complexity dynamically (i.e. by simply running the algorithm and observing its behavior) is impossible, because asymptotic complexity is, well, asymptotic, as the problem size approaches infinity. Ergo, you would need to observe the algorithm for an infinite amount of time. And doing it statically is impossible, since determining the time complexity also determines halting (if the complexity is not infinite, the algorithm halts), which is provably impossible. – Jörg W Mittag Aug 31 '10 at 13:49

2 Answers2

0

The main problem is probably that different algorithms require completely different input. You might be able to write a function that classifies the performance of sorting functions since they all use the same type of input, and you can just generate an increasingly larger set to see how performance degrades.

Emil H
  • 39,840
  • 10
  • 78
  • 97
0

You might be able to write something that can compare complexities on one machine, but as soon as you put your script on another machine things are going to get very confusing. You'd have to figure out some way of calibrating it, and even then it would only work on "perfect" algorithms.

fredley
  • 32,953
  • 42
  • 145
  • 236