CODEWITHSUNDEEP
algorithmtime-complexity
Vinícius Lopes Simões
Vinícius Lopes Simões

Reputation: 355

Algorithm to estimate time complexity of another algorithm

Is it possible to develop an algorithm to estimate the time complexity of another algorithm? I mean, the input would be some algorithm and the output could be the time complexity of it (Big-Oh, Big-Omega, and so on). I could not find anything about it on the web.

Thank you

Upvotes: 2

Views: 70

Answers (1)

xmerge
xmerge

Reputation: 126

Let me extend @interjay's comment a little bit.

The halting problem is asking

if it possible to design a Turing Machine (you may think it as an program in you computer) such that given a Turing Machine (again, think it as a program) it can decide whether or not this input Turing Machine will terminate eventually.

One can prove that it is impossible to design such a Turing Machine. Now let consider you question, if you are able to design an algorithm as you want, you will be able to answer whether a given Turing Machine will terminate or not. That is unfortunately impossible.

Above argument is called "Reduction" which is one of the most popular way to show a given problem is unsolvable.

Upvotes: 2

Related Questions