0
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – clemens Jan 12 '18 at 7:08
  • 1
    $\begingroup$ What do you mean by "asymptotically close"? $\endgroup$ – Raphael Jan 12 '18 at 9:43
  • $\begingroup$ Close to O(1), asymptotically close to no one. $\endgroup$ – raindrop Jan 12 '18 at 19:54
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user82923 Jan 12 '18 at 8:00
  • $\begingroup$ I edited my post to make it clearer. $\endgroup$ – clemens Jan 12 '18 at 8:43
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

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