# Exponential time algorithm

1. Aug 10, 2006

### teng125

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

thanx

2. Aug 10, 2006

### FredGarvin

3. Aug 10, 2006

### 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

4. Aug 10, 2006

### 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?

5. Aug 10, 2006

### 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$$