"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.

I guess you mean like seives like NFS and QS.

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"),

Is n't it the big Oh-upper bound that determines if it is best-since we always consider the worst case scenario. yes,i remember that algorithm of primality in P. thank you for answering. Regards Data. __________________________________________________ Do you Yahoo!? Faith Hill - Exclusive Performances, Videos & More http://faith.yahoo.com