[Solved]: If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

Problem Detail: 

If one refers to 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)?

Asked By : user695652

Answered By : Tom van der Zanden

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56495

3.2K people like this

 Download Related Notes/Documents