Is O(ln n) "exponentially faster" than O(n)?
How should we measure (asymptotic) speedup?

Say we wish to compare two functions, $f(n)$ and $g(n)$, and say something on their asymptotic behavior, that is, how they behave for large enough $n$'s, in the limit $n \to \infty$. 

Let's start with a few examples.


  Example 1:  $f(n)=2n$ and $g(n)=n$.


Here it is obvious that $f$ is "twice as slow" as $g$; This is true for any $n$ and also in the limit. This needs not be the case. For instance


  Example 1.1:  $f(n)=2n$ and $g(n)=n+1000$.


Well, now, for $n&lt;1000$, $f$ is actually faster than $g$. But still, if we take large $n$'s, we want to say that $f$ is twice as slow as $g$, or in other words, the speedup is 2. 

Why 2? Because the ratio between $f$ and $g$, in the limit, is 2.

Let's take a different example to emphasize this issue.


  Example 1:  $f(n)=n+10$ and $g(n)=n$.


Here, $f$ is slightly slower than $g$. What is the speedup between $f$ and $g$? By how much is $g$ faster? The answer is "by 10 clocks". But speedup is measured as a ratio - "twice" as fast means it would take (approx.) twice the time to run the slower function. Here the ratio is approaching 1
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} \to 1$$
That is, the 10 clocks don't make any (multiplicative) difference. Running 10000 clocks and running 10010 clocks, is practically the same (the speedup is $&lt;0.1\%$). 

I hope the above establishes that the (asymptotic) speedup between $f$ and $g$ should be defined as
$$\lim_{n\to \infty} \frac{f(n)}{g(n)}.$$

When the speedup is not a constant, then the best way to describe the speedup is to set $g(n)=k$ and ask how $f(n)$ behaves as a function of $k$. If $f(n) \propto k^2$, then the speedup is "quadratic". If $f(n)\propto k^3$ the speedup is cubic. If $f(n)\propto 2^k$, the speedup is called exponential. Not that it is important to set $g$ as the base unit ($=k$). Otherwise, If we take $f$ as the base unit, then a quadratic speedup translates to $g(n)=\sqrt{k}$, which may be a bit confusing. Maybe its better to think at the other direction: instead of considering the speedup from $f$ to $g$, look at the slowdown from $g$ to $f$. (.. if $g$ is twice as fast as $f$, then $f$ is twice as slow as $g$)

If we agree on this, we can check the speedup between $f(n)=n$ to $g(n)=\log n$.
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{n\to \infty}\frac{n}{\log n}$$
Let's change the limit variable, to make $g$ the base unit for the comparison: set $k=\log n$, then,
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{k\to \infty} \frac{2^k}{k}$$
That is the ratio between them, in the limit, has an exponential gap. As mentioned, this is called exponential speedup.