patternMinor
Is O(ln n) "exponentially faster" than O(n)?
Viewed 0 times
exponentiallythanfaster
Problem
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.
Solution
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.. 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.
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.. 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.
Context
StackExchange Computer Science Q#50350, answer score: 7
Revisions (0)
No revisions yet.