Time complexity of a binary search

[YoungPhysicist]

Binary search works by eliminating half of the objects in a sorted array every time,so shouldn’t it’s time complexity being $O(\log_2 n)$ instead of $O(\log n)$?

 

[mfb]

Where is the difference?

 

[YoungPhysicist]

Where is the difference?

I do get that when the input tends to infinity,the difference between $\log x$ and $\log_2 x$ becomes smaller and smaller,but why don’t they just use $O(\log_2 x)$?

 

[aaroman]

Because a multiplying constant is of no importance in the O notation.

 

[Ibix]

I do get that when the input tends to infinity,the difference between $\log x$ and $\log_2 x$ becomes smaller and smaller,but why don’t they just use $O(\log_2 x)$?

It isn't about limits as n tends to infinity. Do you know how to express the $\log_b x$, where $b$ is any base, in terms of $\log x$?

 

[YoungPhysicist]

Do you know how to express the logbxlogb⁡x\log_b x, where bbb is any base, in terms of logxlog⁡x\log x?

Yes, I do.
$$\log_2 x = \frac{\log x}{\log 2}$$

 

[mfb]

So ln(x) and log₂ only differ by a constant (ln(2)). A constant doesn't matter. $O(\log n) = O(5\log n) = O(46342\log n)$

 

[YoungPhysicist]

So ln(x) and log₂ only differ by a constant (ln(2)). A constant doesn't matter. $O(\log n) = O(5\log n) = O(46342\log n)$

Ohh~~problem solved!

Edit:so this $\log x$ means $\log_e x$ rather than $\log_{10} x$ ?

 

[Ibix]

Ohh~~problem solved!

Edit:so this $\log x$ means $\log_e x$ rather than $\log_{10} x$ ?

It doesn't matter. All bases do the same thing - you just multiply by a constant to change base, and you discard that constant in this case.

 

[YoungPhysicist]

It doesn't matter. All bases do the same thing - you just multiply by a constant to change base, and you discard that constant in this case.

Yeah.Just making sure the ln(x) posted by @mfb isn’t an accident.

 

[Mark44]

Binary search works by eliminating half of the objects in a sorted array every time,so shouldn’t it’s time complexity being $O(\log_2 n)$ instead of $O(\log n)$?

In computer science books $\log(n)$ is usually taken to mean $\log_2(n)$.

In the calculus textbooks I learned from, which was a while ago, $\log(x)$ meant $\log_{10}(x)$, the so-called common logarithm. The notation $\ln(x)$ was reserved for the natural logarithm, or $\log_e$. I'm told that more modern calculus textbooks treat $\log$ and $\ln$ as synonyms.

 

[mfb]

Yeah.Just making sure the ln(x) posted by @mfb isn’t an accident.

I used ln(x) to avoid ambiguity.

Computer science read log(x) as base 2, mathematics and most of physics will see it as base e, chemistry will see it as base 10, ...

 

[YoungPhysicist]

Computer science read log(x) as base 2, mathematics and most of physics will see it as base e, chemistry will see it as base 10, ...

woah!