# Is $O(\log_2 n)$ close to $O(n)$ or $O(1)$?

We know that asymptotically $O(1)$< $O(\log_2 n)$ < $O(n)$, but $O(\log_2 n)$ is asymptotically close to $O(n)$ or $O(1)$?

• Note: We're talking about Big O. The logarithm base is irrelevant. Thus, $O(\log n) = O(\log_2 n)$ since $\log_c n = \log n / \log c$. – clemens Jan 12 '18 at 7:08
• What do you mean by "asymptotically close"? – Raphael Jan 12 '18 at 9:43
• Close to O(1), asymptotically close to no one. – raindrop Jan 12 '18 at 19:54

## 3 Answers

As far as I understand your question, you have to take a look at the differences: $O(\log n - 1) = O(\log n)$ versus $O(n - \log n)$. Since

\begin{eqnarray} n - \log n & \stackrel!> & \log n\\ n & > & 2 \log n\\ \end{eqnarray}

you have $O(\log n) \subset{} O(n - \log n)$. The difference to $O(n)$ grows faster than the difference to $O(1)$.

Thus, $O(\log n)$ is closer to $O(1)$ than $O(n)$.

• I don't know which part I was not able to make it clear. These functions are used to measure run-time of given algorithm. So, I want to know among given two which grows very close to logn? – user82923 Jan 12 '18 at 8:00
• I edited my post to make it clearer. – clemens Jan 12 '18 at 8:43

In some areas, we use $\widetilde O$ instead of $O$ to ignore $\mathsf{poly}(\log n)$ terms. The reason is that $\mathsf{poly}(\log n)$ terms are very small compared to polynomial terms such as $n^\epsilon$, even for an arbitrarily small $\epsilon>0$.

So, roughly you can say $O(\log n)$ is closer to $O(1)$.

Here is a similar question:

I know that $1 < 10 < 10^6$, but is $10$ close to $1$ or to $10^6$?

I'm not sure what kind of answer you expect – you'll have to explain when two functions $f,g$ are asymptotically close. Often we consider $f,g$ to be asymptotically close if $f = \Theta(g)$. Other times, we also allow logarithmic differences, that is, we say that $f,g$ are asymptotically close if $f = O(g \log^C g)$ and $g = O(f \log^C f)$ for some constant $C > 0$. Under both of these definitions, $\log n$ is asymptotically close to neither $1$ nor $n$.