Program/algorithm to find the time complexity of any given program

Question

I like to know whether it is possible to "write a program or algorithm" to find the time complexity of any given program taken as input.

Input : any program (P) [in any language or of a particular language]

Output : time complexity of that program (P).

Have there been any prior attempts to write such a program? Are there any algorithms available for this purpose?

If so please provide the necessary links, references or with any kind of guidance possible.

Answer 1

No. It's not possible. This is a form of the halting problem.

Answer 2

Proving the complexity of an arbitrary algorithm is not possible but in principle you could estimate it:

1. choose n, the size of the input
2. run the algorithm
3. observe t(n), the time needed to run the algorithm for input of size n
4. choose another n, repeat steps 2 and 3 until you have a lot of data
5. regress t(n) on n, n^k, log(n), n log(n), n!, or any other term that might be appropriate
6. choose a term with statistical significance and declare that to be your estimated complexity of the algorithm

There are any number of pitfalls to this approach

1. This will not prove anything, only estimate
2. If t(n) gets really large for large n, it will take a long time to collect enough data for your analysis

3. There are many ways that this approach can be fooled unless you use huge values of n. For example, this algorithm will look like O(1) unless you use astronomical values for n

   sleep for 10 days
   run an O(n log(n)) sorting algorithm
   

And other SO users can come up with many more. But in some cases, like when you do a complexity analysis of an algorithm and want to verify it empirically, this is still a useful approach.

Answer 3

can't we introduce some more variables in the algorithm itself and find the complexity the same way we do it manually. like for example we can have a variable in an insertion sort say n=0 which keeps the track of the entire looping part of the algorithm and then give the answer as O(n^2)

Answer 4

Well I think you do this by assuming all cases. 1:Like first make a module which can extract each of the instruction 2: Do make a database of instruction to match up with the program instruction. 3: calculate the complexity by fetching the appropriate time complexity set by you in database and that's all.