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: How to prove?

  1. Feb 24, 2005 #1
    For a positive natural number n, we use
    [tex]
    |n|= \log_{2}n
    [/tex]
    as the measure of the size of n (which is the number of bits in n's binary representation). however, in most cases the size of n can be written as log n without giving an explicit base (the omitting case is the natural base e). Show that for any base b>1,
    [tex]
    \log_{b}n
    [/tex]
    provides a correct size measure for n, i.e., the statement "a polynomial in the size of n" remains invariant for any base b>1.


    This was a problem in my homework for cryptography...

    I understand the first part of the problem, which basically means that for any base, b:

    [tex]
    \log_{b}n=|k| => b^{[k]+1} > n
    [/tex]
    where [k] equals the floor of k.

    but beyond that, I really have no idea...

    thanks for any help

    matt
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted