What is the difference between optimality and efficiency?

Question

Could someone differentiate between optimality and efficiency? Provide a definition for each term if possible.

Answer 1

In both cases there is a criteria. In programming or algorithms they usually both refer to one of: operations, time or memory and the method of measuring.

Optimal - often marked as OPT in algorithms - is the best solution according to the criteria. It means, that better solution doesn't exist. Watch out! There can be more than one OPT solutions!

Efficient means nothing by itself but can be used in combine with a comparator. It means that you can say that one algorithm is more efficient that the other one which means, that it's faster or less memory consuming.

The most efficient solution will be the optimal one.