Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with Logarithms

  1. Dec 4, 2004 #1
    I am working on some homework about binary searches. In case you don't know, a binary search of x items takes at most log base 2 (x) searches to find what you are looking for (assuming it is sorted data of course). Now we are asked if using a phone book as an example, we have a reference to the first name on each page, how does that change the at most number of searches.

    In other words, if I have x names in the phone book with y names on z pages (x = y*z). How much is that different than log base 2 (x). Using this method it takes at most log base 2 (y) searches to find the page and then log base 2 (z) searches to find the name on that page ( log base 2 (y) + log base 2 (z) ). It seems to be the case that log base 2 (x) = log base 2 (y) + log base 2 (z). Can any one prove this for me? Thanks.
  2. jcsd
  3. Dec 4, 2004 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's not clear what you want to prove. If you sinply want to prove that, given x = yz, then log(x) = log(y) + log(z) simply recall the product rule for logarithms : log(yz) = log(y) + log(z).
    ...but I suspect you are asking for something else.

    I'm not sure, so I'll allow you to clarify.
    Last edited: Dec 4, 2004
  4. Dec 4, 2004 #3
    OR that 2^(x)*2^(y)=2^(x+y)
  5. Dec 4, 2004 #4
    Actually that was all I was asking for, thanks!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook