At 05:44 AM 10/07/2002 -0700, gfgs pedo wrote: >In the case of algorithms is the best algorithm always >the best solution to the problem,be the algorithm with >a constant run time or randomised algorithm. > >i.e is the best solution always the optimal solution >for a problem.
"Best" means "best for some specific objective". "Optimal" means the same thing as "best". Depends on what you want to do. There are countless examples of problems for which different algorithms scale differently by problem size, e.g. for N=10, Algorithm A is the fastest solution, but for N=1000, Algorithm B is much faster. There are also lots of examples of problems for which one algorithm has an asymptotic lower bound that's the lowest known (or some other type of "best"), but a different algorithm is usually much faster most of the time, so most people use that instead (or use some hybrid like running both in parallel or whatever.) Back in August there was that O(log(n)^12) deterministic algorithm for primality testing (and some arguments for running it in logn^6 time or maybe even logn^3 time), compared to the usual probablistic algorithms that run in logn^3 time per factor of 2-4. For relevant-sized numbers, cranking the probablistic algorithm 20-40 times is much faster than the logn^12 or logn^6 versions, and the consequences of getting a Carmichael number once every billion runs aren't very severe.
