Rapsinincke

2022-07-04

I am reading "Problem Solving with Algorithms and Data Structures using Python" and the author is currently explaining the relation between comparisons and the Approximate Number of Items Left in an Ordered List.
I am struggling to perform the conversion of: $\left(\frac{n}{{2}^{i}}\right)=1$ to i=logn
I put this expression into MathWay and got back $i=lo{g}_{2}\left(1\right)$ and I'm a little confused on how these results are equivalent. I'm pretty rusty with logarithms so if you could help explain this conversion to me I'd greatly appreciate it.

Freddy Doyle

Expert

So you have
$\frac{n}{{2}^{i}}=1$
Multiplying both sides by ${2}^{i}$, one gets
$⇒\frac{n}{{2}^{i}}×{2}^{i}=1×{2}^{i}$
You can cancel the ${2}^{i}$s on the left hand side, giving us
$n={2}^{i}$
Now - we want some way of turning ${2}^{i}$ into just i. How do we do this? Well, applying log base 2 to both sides gives us
$⇒{\mathrm{log}}_{2}\left(n\right)={\mathrm{log}}_{2}\left({2}^{i}\right)$
The right hand side, by the definition of the Logarithm is saying "what number do I raise 2 by to get ${2}^{i}$?" Clearly, the answer is i. And so
$⇒i={\mathrm{log}}_{2}\left(n\right)$
Edit: So technically, the Logarithm in the book should also be base 2; however, I think he may have left it out for 2 potential reasons:
(1) As you say, in many places log without a base specified usually refers to base 10; However, Mathematicians also use log without a specified base to mean base e (where e is Euler's number - don't worry if you don't know what this is) - it could be that the author is just using log without a base to mean base 2 (unlikely, I think - but possible).
(2) I noticed he talked about big O notation. In big O notation, it doesn't really matter whether it's $O\left({\mathrm{log}}_{2}\left(n\right)\right)$ $O\left({\mathrm{log}}_{10}\left(n\right)\right)$ etc etc. One property of the Logarithm is that
${\mathrm{log}}_{a}\left(n\right)=k×{\mathrm{log}}_{b}\left(n\right)$
That is, the log function in one base can be written as a scalar multiple (just some number) multiplied by the log of another base. And in big O notation
$k×O\left(f\left(n\right)\right)=O\left(f\left(n\right)\right)$
So it doesn't really matter which base you put (provided the base is, of course, positive). Ultimately, the choice is arbitrary in big O notation, and so many times people just write log with the base ommitted. I guess in some sense, you could say there is only really one log function, and the base only really affects what multiple of it you take.

Do you have a similar question?