CODEWITHSUNDEEP
algorithmtime-complexity
diiva
diiva

Reputation:

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

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.

Upvotes: 9

Views: 11270

Answers (4)

Manthan Shah
Manthan Shah

Reputation: 119

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)

Upvotes: 0

Shahid
Shahid

Reputation: 1

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.

Upvotes: -3

mob
mob

Reputation: 118605

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.

Upvotes: 4

erickson
erickson

Reputation: 269667

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

Upvotes: 30

Related Questions