I was thinking about why computational complexity theory considers algorithms executable in polynomial time to be efficient, and those executable in exponential time to be inefficient. At first glance, this boundary seemed rather arbitrary, but then I thought about this:
$${\frac{d^n}{dx^n}}[a^x] = (log(a))^na^x$$
The exponential function is the lowest in the hierarchy of functions whose $(n+1)$th derivative can be expressed as the product of a constant factor and its $n$th derivative. To get the derivative of a polynomial $ax^n_1 + bx^n_2 + ... $, however, the polynomial must be divided by some function of $x$.
If exponential functions are divided into two classes: those with bases less than $e$, and those with a base of $e$ or higher, the significance of the above observation becomes clearer. For those in the first class, $log(a) < 1$, and therefore the constant factors by which the successive derivatives of the functions decrease themselves undergo exponential decay. For those in the second, by the same logic, the successive derivatives of the functions either stay the same or actually increase! (Of course, composite functions such as $2^{2x}$ cannot be divided into these classes so easily, but my point remains the same.)
I was curious whether this observation, either directly or indirectly, influenced the classification of algorithms as either efficient or inefficient.
Few years ago I listened a course “Complexity Theory” by Prof. Dr. Klaus Wagner, and I think that the reason for such the consideration is very deep. I can see its roots down to Main Theorem of Algorithm Theory and Church's Thesis, stating that every function computed by an algorithm in an intuitive sense can also be computed by a Turing machine (see p. 6). Next, the different types of algorithms are polynomially related (see p. 15). At last, “The classes FP and P are of great practical interest because every function which can be computed (every problem which can be solved) by a computer in a reasonable amount of time is in FP (P, resp.) (see p. 24).