1. Not finding help here? Sign up for a free 30min 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!

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
    Gold Member
    2016 Award

    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
    Gold Member
    2016 Award

    @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
    Gold Member
    2016 Award

    Yes I did - my apologies :D
    Edited.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Help With Logarithms
  1. Logarithmic Help (Replies: 2)

  2. Help with logarithms (Replies: 4)

  3. Logarithm [Help] (Replies: 1)

  4. Logarithm Help (Replies: 5)

  5. Logarithms help (Replies: 3)

Loading...