Definition of efficiency versus complexity of algorithm

When I read introductory textbooks I get contradictory answers. In some cases efficiency and complexity are treated the same and the big-O notation is used to indicate that (for example) for an O(n) algorithm the time to execute is linearly proportional to the input dataset size.

From other sources I have read that efficiency is a measure of the computing resources required to execute an algorithm, but not the same as the complexity of the algorithm. So for example is it possible to have an algorithm (say to multiply two decimal numbers) that is efficient in terms of its resources (it does not need much to execute) but is complex in that as the input dataset increases in size the time to execute is O(n^2) ???

An algorithm is often called "efficient" if its runtime is short, compared to the inherent difficulty of the problem.

For example, you cannot sort arbitrary arrays by comparing keys in less than O (n log n). Once sorted you can lookup values in O (log n). Looking up a value in the sorted array by doing a linear search has lower complexity then sorting the array, but it is inefficient because linear search takes time O (n) and could be done in O (n log n).

StackExchange Computer Science Q#71858, answer score: 2