Understanding Polynomial Time Complexity

[teng125]

can sombody pls explain to me what does exponential time algorithm means??

thanx

 

[FredGarvin]

It would help us if we knew the context of the question. Is this a programming problem of some kind?

EDIT: A quick Google search provided
http://ourworld.compuserve.com/homepages/anima/expon.htm
http://foldoc.org/?exponential-time+algorithm
http://en.wikipedia.org/wiki/Exponential_time

 

[teng125]

it is just some very basic computer question which is algorithm.It is not a programming problem.
It means an algorithm which take exponential time to complete and another type is it takes polynomial time to compete an algorithm.

Therefore,i do not understand what it means by exponential time and polynomial time

 

[0rthodontist]

If an algorithm takes exponential time, that usually means that it can be done in
$$\Theta (a^n)$$ time for some constant a.
If an algorithm takes polynomial time, that usually means it can be done in
$$\Theta (P(n))$$ time for some polynomial P.
Are you familiar with $$\Theta$$, O, or $$\Omega$$ notation?

 

[buddyholly9999]

Just to show a quick example of polynomial time. Say you have two nested for loops,
for (i=1; i<n; i++) {
for (j=1; j<n; j++) {}
}

we can see that j goes to n as i = 1, then j goes to n as i = 2...you see a pattern? j goes to n, n times. Thus our running running time is
n * n ...which also happens to be n^2...this is what is meant by polynomial time..a run time that can be expressed in polynomial form..$$a_nx^n + a_{n-1}x^{n-1} + \cdots + a_0$$