principleMinor
If O(log n) vs O(n) is exponential what is O(1) vs O(n)?
Viewed 0 times
exponentialwhatlog
Problem
If one refers to using an
how would one refer the speedup gained by using an
O(log n) instead of an O(n) algorithm as an exponential speedup, how would one refer the speedup gained by using an
O(1) algorithm vs an O(n)?Solution
There's no name for that, but the closest would be "infinite" speedup. $O(\log n)$ is considered an exponential speedup over $O(n)$, because $n$ is exponential in $\log n$: if we take the exponential function $f(n)=2^n$, we get $f(\log n)=2^{\log n}=n$.
However, $n$ isn't anything in $1$: there's no way to recover $n$ from $1$, no matter how quickly the function $f$ that we take grows, $f(1)$ will always be a constant (and never equal $n$). As $n\to \infty$, $1$ becomes infinitely smaller than $n$.
However, $n$ isn't anything in $1$: there's no way to recover $n$ from $1$, no matter how quickly the function $f$ that we take grows, $f(1)$ will always be a constant (and never equal $n$). As $n\to \infty$, $1$ becomes infinitely smaller than $n$.
Context
StackExchange Computer Science Q#56495, answer score: 4
Revisions (0)
No revisions yet.