answersLogoWhite

0

Do you mean, "the difference between an algorithm that runs in polynomial time, and one that runs in exponential time".

First a real quick review. A polynomial is any equation of the form

y = cmxm + ... + c2x2 + c1x + c0 ,

where ci are constants

An exponential function is something of the form

y = cx

These functions grow much faster than any polynomial function.

So, if T(n) describes the runtime of an algorithm as a function of whatever (# of inputs, size of input, etc.)., and T(n) can be bound above by any polynomic function, then we say that algorithm runs in polynomial time.

If it can't be bound above by a polynomial function, but can be bound above by an exponential function, we say it runs in exponential time.

Note how ugly an exponential algorithm is. By adding one more input, we roughly double (or triple, whatever c is) the run-time.

User Avatar

Wiki User

15y ago

What else can I help you with?

Related Questions

Example of fundamental difference between a polynomial function and an exponential function?

fundamental difference between a polynomial function and an exponential function?


How can i Differentiate between an algebraic expression and polynomial?

A polynomial is always going to be an algebraic expression, but an algebraic expression doesn't always have to be a polynomial. An algebraic expression is an expression with a variable in it, and a polynomial is an expression with multiple terms with variables in it.


What is the difference between P and NP complexity classes?

P 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


What is the difference between exponential and polynomial time complexity?

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.


What is the trend between 4 and 5 seconds?

Increasing between the two. From just two points, there is no way of telling whether it is linear or polynomial or exponential or power.


What is a chart used for in math?

To present information is a visual form to give a summary.In statistics, in particular, the nature of relationships between variables (linear, polynomial, exponential etc) is easier to see in a chart than in a table of numbers.To present information is a visual form to give a summary.In statistics, in particular, the nature of relationships between variables (linear, polynomial, exponential etc) is easier to see in a chart than in a table of numbers.To present information is a visual form to give a summary.In statistics, in particular, the nature of relationships between variables (linear, polynomial, exponential etc) is easier to see in a chart than in a table of numbers.To present information is a visual form to give a summary.In statistics, in particular, the nature of relationships between variables (linear, polynomial, exponential etc) is easier to see in a chart than in a table of numbers.


How do we differentiate between a quadratic equation and an exponential equation?

a quadratic equation must be in this form ax^2+bx+c=0 (can either be + or -) an exponential just means that the function grows at an exponential rate f(x)=x^2 or x^3


What is the difference between polynomial and non polynomial time complexity?

Polynomial vs non polynomial time complexity


Difference between np and np complete?

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.


Difference between deterministic and nondeterministic algorithm in design and analysis of algorithm?

Algorithm is deterministic if for a given input the output generated is same for a function. A mathematical function is deterministic. Hence the state is known at every step of the algorithm.Algorithm is non deterministic if there are more than one path the algorithm can take. Due to this, one cannot determine the next state of the machine running the algorithm. Example would be a random function.FYI,Non deterministic machines that can't solve problems in polynomial time are NP. Hence finding a solution to an NP problem is hard but verifying it can be done in polynomial time. Hope this helps.Pl correct me if I am wrong here.Thank you.Sharada


What is the relationship between binomial and a polynomial?

A binomial is a polynomial with exactly 2 terms.


What are the key considerations when solving the pseudo-polynomial knapsack problem efficiently?

When solving the pseudo-polynomial knapsack problem efficiently, key considerations include selecting the appropriate algorithm, optimizing the choice of items to maximize value within the weight constraint, and understanding the trade-offs between time complexity and accuracy in the solution.