top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Is there any standard way to calcuate space and time complexity for any program/algorithm?

+1 vote
352 views
Is there any standard way to calcuate space and time complexity for any program/algorithm?
posted Apr 25, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+2 votes

I don't think there is any standard method available for calculating complexity or any formula/program where you need to paste only your program to get complexity of it as output. For calculating complexity you must know everything about complexity but somewhere you can reduce this by using master theorem ,in case of recursion, or easily predictable in case of simple loop programs.In case of large programs you need to take care of all lines of code,keywords in them which will help you for better prediction of complexity so you need to learn more.
This type of problem falls under Halting problem category- In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine.The halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.
Reference: https://en.wikipedia.org/wiki/Halting_problem

answer Apr 29, 2016 by Shivam Kumar Pandey
...