I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear the phrase "exponential speedup". I'd like to avoid overselling my work.

  • $\begingroup$ Sublinear sounds fancy, I might go with it. However, I can you give a mathematical reasoning, why that cannot be considered an exponential speedup? I can process exponentially more data in the same time compared to before. $\endgroup$ Dec 5 '15 at 15:26
  • $\begingroup$ I wouldn't use "exponentially", unless an actual exponent could be directly indicated, somehow. $\endgroup$ Dec 5 '15 at 15:51
  • 3
    $\begingroup$ @AndréSouzaLemos $2^{\log n}\to\log n$. $\endgroup$ Dec 5 '15 at 15:55
  • 3
    $\begingroup$ Beware of associating "exponential" with NP! We don't know that NP-complete problems require exponential time. Also, on a more subtle level, it doesn't really make sense to talk about "going from NP to P". Complexity classes are collections of problems; what you've done is produce a new algorithm (see our reference question for more). $\endgroup$ Dec 5 '15 at 15:58
  • 1
    $\begingroup$ Of course it is an exponential speedup. $\endgroup$ Dec 5 '15 at 16:32

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.