I am reading "Problem Solving with Algorithms and Data Structures using Python" and the author is cu
Rapsinincke
Answered question
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: to i=logn I put this expression into MathWay and got back 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.
Answer & Explanation
Freddy Doyle
Beginner2022-07-05Added 20 answers
So you have
Multiplying both sides by , one gets
You can cancel the s on the left hand side, giving us
Now - we want some way of turning into just i. How do we do this? Well, applying log base 2 to both sides gives us
The right hand side, by the definition of the Logarithm is saying "what number do I raise 2 by to get ?" Clearly, the answer is i. And so
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 etc etc. One property of the Logarithm is that
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
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.