[Fyre4ce]

I'm not a programmer, but a programming student. I was wondering if anyone out there actually encounters exponential algorithms. I know it's possible to write a simple one...
<BLOCKQUOTE><font size="1"face="Geneva, Verdana, Arial">code:</font><HR><pre><font size=1 face=courier>
void eatTimeExponentially(int n)
{
int a=<font color = blue>0</font>, b=<font color = blue>1</font>;

for(int i=<font color = blue>0</font>; i&lt; pow(<font color = blue>2</font>,n); i++)
{ swap(a, b);}
}
</font>[/code]
...but are there any practical algorithms that take exponential time?

[parallax]

<STRONG>
...but are there any practical algorithms that take exponential time?</STRONG>

Hehe, the two are mutually exclusive! Practical is pretty much defined as polynomial or better.

The standard recursive Fibonacci algo (return f(n-1) + f(n-2)) I believe is exp time. Yuck!

[JBL]

I am not quite sure what you are asking for. If you take the obvious solution to the traveling salesman problem (find the shortest route through n points) takes n! time. (This is faster than exponential so I don't know if it qualifies.) I don't know if there is a better algorithm but I do know that there is no known algorithm that is polynomial. It is an open question whether such problems can be done in polynomial time.

[Fyre4ce]

I believe that factorial is slower than exponential. Think about it: every time n is increased by one in exponential, the time gets multiplied by some constant number (the base). But in factorial, every time n is increased by one, the time gets multiplied by an increasingly larger number. It's only a matter of time before that number eclipses the base of the exponential. Or, the limit of (n! / e^n) as n -&gt; infinity is infinity.

Since we're on the topic of algo analysis...

Why is quicksort faster than some bin sorts, like the radix sort? If you assume that the size of your integers increases with their number (worst-case), then radix is O(n log n). But if the size of the integers is held constant, then radix is O(n). Quicksort is at best O(n log n). I know radix space-intensive, but with 512 MB RAM costing under $20 these days, isn't the speed worth it? There's also a lot of overhead, but for sorting very large arrays of simple integers, radix makes a lot more sense to me than quicksort.

[davechen]

It's been a looooong time since I was an undergrad taking theory classes, but aren't n! and exponential essentially the same thing? other than a constant.

You can make any algorithm n! by throwing in useless loops or whatever. The more interesting question is what algorithms can only be solved in exponential time. As was mention traveling salesman is a classic problem. I think some others include coloring a map or the packing problem. Map coloring asks the question can you color a map with K colors such that no two neighbors have the same colors. The packing problem is, given a set of boxes of arbitrary sizes, what's the optimal way of putting them in a knapsack.

All these NP complete problems, currently have to be solved by trying every possible combination. I.e. there's no easier way of doing it. Hence the factorial.

Talking about sorting, as you say, you need a lot of memory to handle large problems with radix sort. There are always situations where you don't have enough memory, such as dealing with big, terabyte databases. Things like the IRS, or medical records of an entire state.

On the other hand, half the time, I just hack up bubble sort, since I'm only dealing with a few hundred items. It's easy to code and the constants are small. For small N, setup time and constants are more the problem.

dave

[tie]

n! \approx \sqrt{2\pi n} (n/e)^n = \sqrt{2\pi n} e^{n(\ln n - 1)}

So n! is exponential.

[DaGuy]

Dudes/Dudettes,

Factorial growth is faster than exponential. For n = positive integer, we have

n! = 1*2*3*...*n

e^n = e*e*e*...*e (n times)

So, this means that after n=2 we see that every factor of the factorial function is
larger (and getting bigger and bigger) than "e" which is approx. 2.78 or something like that. In other words

e&lt; 3 & e&lt;5 & e&lt;6 etc...

So, factorial growth leaves exponential growth in the dust after some not too large integer.

[Wixar]

tie wrote:

n! \approx \sqrt{2\pi n} (n/e)^n = \sqrt{2\pi n} e^{n(\ln n - 1)}

So n! is exponential.

Check your conclusion. You have a term (n/e)^n, which is order n^n, which is slower than exponential.

Indeed, factorial is of approximately the same order as n^n.

-Peter

[Ghoser777]

How would you describe finding the nth prime number? There's several algorithms, the fastest that I know of takes your seed (2), checks to see if any primes less than or equal to the square root of the seed (in the first case, there are none). If the seed is not divisible by any past primes, then it is added to an array of found primes. If your not done, increment the seed and repeat the process until you obtain an array of n primes.

F-bacher

[tie]

Originally posted by Wixar:
<STRONG>Check your conclusion. You have a term (n/e)^n, which is order n^n, which is <font color = red>slower</font> than exponential.

Indeed, factorial is of approximately the same order as n^n.
</STRONG>

n! = O( e^{n log n} )

exp(n log n) is of course worse than exp(n), but normally, we define exponential as O( e^poly(n) ), so n! is exponential. We can also, of course, subdivide the class of "exponential" algorithms according to the degree of the polynomial in the exponent, or whatever.

[lgerbarg]

Originally posted by Fyre4ce:
<STRONG>I'm not a programmer, but a programming student. I was wondering if anyone out there actually encounters exponential algorithms. I know it's possible to write a simple one...
&lt;BLOCKQUOTE&gt;&lt;font size="1"face="Geneva, Verdana, Arial"&gt;code:&lt;/font&gt;&lt;HR&gt;&lt;pre&gt;& amp;lt;font size=1 face=courier&gt;
void eatTimeExponentially(int n)
{
int a=&lt;font color = blue&gt;0&lt;/font&gt;, b=&lt;font color = blue&gt;1&lt;/font&gt;;

for(int i=&lt;font color = blue&gt;0&lt;/font&gt;; i&lt; pow(&lt;font color = blue&gt;2&lt;/font&gt;,n); i++)
{ swap(a, b);}
}
&lt;/font&gt;&lt;/pre&gt;&lt;HR&gt;&lt;/BLOCKQUOTE&gt;
...but are there any practical algorithms that take exponential time?</STRONG>

The classic example of an exponential algorithm that is used in the real world is the Simplex Algorithm for Linear programming. For years there was also a polynomial algorithm, but the constants were actually so bad that for any data set someone was likely to use Simplex was faster. Nowadays there is a slightly faster polynomial alogrithm (Karamakar's method, I think), but it is very complex compared to Simplex, and is usually not worth the effort of implementing.

Louis

[Fyre4ce]

Factorial is much much slower than exponential. n^n, in turn, is slower than factorial. I can't imagine any n^n algo! It would be unbelievably slow for any large n values.

[Fyre4ce]

I decided to play with some numbers and compare some different order algos. The results are listed below.



A few notes:

1) The numbers you see there are the order of magnitude, or the power of ten. So when there's a "4" that means 10^4, or 10,000 time units.

2) To put those numbers in perspective (assuming the constants are the same), if an O(n^2) algo takes one nanosecond with n=100, an O(e^n) algo would take 30,000 billion years! Heh, pretty cool.

3) I had a little help from Mathematica for the larger numbers (magnitude &gt; 1000). I had to stop though, because the amount of time Mathematica was taking, especially for the factorial one, was growing at an undesirable rate. I noticed that calculating the 100,000 one took a few seconds. Calculating the 1 million took three minutes. I didn't want to try 10 million, let alone 1 billion. At that point (10^million time units) it becomes moot, I would imagine.

4) Notice how fast O(log(n)) is. It's incredible. It can process n=1 trillion at ~10% the speed of n=10.

5) O(n) and O(n log(n)) are very close in speed. They are the same order of magnitude up to n=1 trillion.

6) There is a huge distinction between polynomial and exponential. Even O(n^10) is almost infinitely faster than O(e^n) for larger values of n. O(n!) is much much slower than O(e^n), and almost as slow as O(n^n), the worst of all.

Hope you found that enlightening!