1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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. Jul 1, 2013 #1
    I'm having trouble understanding the last two lines of a recurrence relation:

    2(log2 n) + kn
    = n + log2 n * n

    I get the rest of the recurrence relation, but I don't understand how those two became equivalent. Where did k go? Where did + n come from? and what happened to the 2?

    Here is the rest of the relation in case it is needed to understand those two lines:
    T(1) = 1

    T(n) = T(n/2) + T(n/2) + n
    = 2 T(n/2) + n

    = 2 [2 T(n/4) + (n/2)] + n
    = 4 T(n/4) + 2n

    = 4 [2 T(n/8) + (n/4)] + 2n
    = 8 T(n/8) + 3n

    = ...
    = 2^k T(n/(2^k)) + k n

    Suppose (n/(2^k)) = 1:
    Then, n = 2^k => k = log n

    = 2^(log_2 n) * T(1) + k n
    = 2^(log_2 n) * 1 + k n
    = 2^(log_2 n) + k n
    = n + (log_2 n) * n

    => O(n log n)
     
  2. jcsd
  3. Jul 2, 2013 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    From the rest of the relation:
     
  4. Jul 2, 2013 #3
    What value do I raise the constant "2" to, in order to resolve the function 2^n?

    That is what 2^(log2 n) is saying.
     
  5. Jul 2, 2013 #4

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    @theintarnets: sherrellbc has provided a good hint:
    i.e. what is the definition of the logarithm?

    ##a^b=c## then ##\log_a(c)=b## so if you do ##a^{\log_a(c)}## .. what do you get?
    (Try it out using base 10.)
     
    Last edited: Jul 2, 2013
  6. Jul 2, 2013 #5
    I was making a comment. I think you mistook me for the OP.
     
  7. Jul 2, 2013 #6

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    Yes I did - my apologies :D
    Edited.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted