Wiki User
∙ 2014-05-16 16:07:12Polynomial vs non polynomial time complexity
Wiki User
∙ 2014-05-16 16:07:12P is the class of problems for which there is a deterministic polynomial time algorithm which computes a solution to the problem. NP is the class of problems where there is a nondeterministic algorithm which computes a solution to the problem, but no known deterministic polynomial time solution
A problem is 'in NP' if there exists a polynomial time complexity algorithm which runs on a Non-Deterministic Turing Machine that solves it. A problem is 'NP Hard' if all problems in NP can be reduced to it in polynomial time, or equivalently if there is a polynomial-time reduction of any other NP Hard problem to it. A problem is NP Complete if it is both in NP and NP hard.
That means that the running time of a program is proportional to some power of the input size.
Algorithms which have exponential time complexity grow much faster than polynomial algorithms. The difference you are probably looking for happens to be where the variable is in the equation that expresses the run time. Equations that show a polynomial time complexity have variables in the bases of their terms. Examples: n^3 + 2n^2 + 1. Notice n is in the base, NOT the exponent. In exponential equations, the variable is in the exponent. Examples: 2^n. As said before, exponential time grows much faster. If n is equal to 1000 (a reasonable input for an algorithm), then notice 1000^3 is 1 billion, and 2^1000 is simply huge! For a reference, there are about 2^80 hydrogen atoms in the sun, this is much more than 1 billion.
Algorithms which have exponential time complexity grow much faster than polynomial algorithms. The difference you are probably looking for happens to be where the variable is in the equation that expresses the run time. Equations that show a polynomial time complexity have variables in the bases of their terms. Examples: n^3 + 2n^2 + 1. Notice n is in the base, NOT the exponent. In exponential equations, the variable is in the exponent. Examples: 2^n. As said before, exponential time grows much faster. If n is equal to 1000 (a reasonable input for an algorithm), then notice 1000^3 is 1 billion, and 2^1000 is simply huge! For a reference, there are about 2^80 hydrogen atoms in the sun, this is much more than 1 billion.
"Running Time" is essentially a synonym of "Time Complexity", although the latter is the more technical term. "Running Time" is confusing, since it sounds like it could mean "the time something takes to run", whereas Time Complexity unambiguously refers to the relationship between the time and the size of the input.
NP stands for Nondeterministic Polynomial time, and is a class of complexity of problems. A problem is in NP if the computing time needed grows exponentially with the amount of input, but it only takes polynomial time to determine if a given solution is correct or not.It is called nondeterministic because a computer that always automatically chooses the right course of action in each step would come up with a correct solution in polynomial time.
what do you mean by time and space complexity and how to represent these complexity
time complexity is 2^57..and space complexity is 2^(n+1).
Time complexity :: The amount of computer time the program needs to run it to completion. Space complexity :: The amount of memory it needs to run to completion.
There is no time difference between them.
calculate time complexity of heap sort