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

Approximating logarithmic series

  1. Dec 23, 2015 #1
    Can anybody tell me how this is possible
    Capture.PNG
     
  2. jcsd
  3. Dec 23, 2015 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It looks to me as if it isn't possible in the first place. Who claims it is ? Any restrictions on n and h ?
    I see a common factor n in front and then something on the left that depends on n, whereas the remainder on the right does not depend on n.
     
  4. Dec 23, 2015 #3
    Please check this link
    http://sarielhp.org/teach/2003/b_273/notes/12_recc.pdf
     
  5. Dec 23, 2015 #4

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, that's a start. Any more things potential helpers should know ? Such as: lg means base-2 logarithm (contrary to what wolfram thinks)

    I managed to find lectures 10 and 11 as well, but drown in the understanding what the symbols stand for. I don't have a good impression of the recursion tree and am surprised to see ##a## and ##b## disappear (into 2 and 2 ?) and to see ##f## disappear as well. On the other hand an ##H## appears but isn't explained and a ##L## is explained but does not appear [edit]ah, sorry: I see: L is the number of terms in ##T(n)##.
     
  6. Dec 23, 2015 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Is this supposed to hold for arbitrary "n" and "h"? If so we can check by taking specific values for n and h. If we take, say, n= h= 1, the formula becomes [itex]\frac{2}{log(2)- 0}= \frac{2}{1}[/itex] which clearly is not true unless the logarithm is to be "base 2". Is that the case?
     
  7. Dec 23, 2015 #6

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Formally, it looks like they replace the summation index ##i## by ##j=\lg n-i##, as that would give ##\sum_{j=\lg n-1}^1\frac{1}{j}##. Then they rename the summation index ##i##.

    EDIT: sorry, that's for the equality on the first page in the linked pdf, not the equality in post 1. My confusion.
     
  8. Dec 23, 2015 #7
    Actually I've seen lots of places where they have done it
    See the below link at example the guy has done the same thing
    http://clrs.skanev.com/04/problems/03.html
     
  9. Dec 23, 2015 #8
    logarithm is base 2
     
  10. Dec 23, 2015 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The thing you posted is false. However, the specific step in the link is true. So please be careful when copying something next time.
    Try to change variables ##i\rightarrow \log(n) - i##.
     
  11. Dec 23, 2015 #10

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Note the subtle differences between Sariel and Skanev ! The former is a bit sloppy writing ##\lg(n/2) = \lg(n-1)## when he means ##\lg(n/2) = (\lg n-1)##.

    And yes, Wolfram allows ##\lg## to be the base-2 logarithm, a sensible choice in algorithm analysis - so I was wrong to mope about that. Not used to the context, I am.

    So: Picked up some of the vernacular, and Skanev subtask 5 helps out by being a lot more meticulous. Check it out (or do I have to spell it out ?)

    [edit] ah, ##\mu m## was faster.
     
    Last edited: Dec 23, 2015
  12. Dec 23, 2015 #11

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Yes, nothing wrong with it.
    I was confused because the equality in the question and the somewhat similar equality in the linked pdf are different.
     
  13. Dec 23, 2015 #12

    mathman

    User Avatar
    Science Advisor
    Gold Member

    There appears to be an error in your equation. I looked up your reference and the upper limit is log(n)-1 not h-1. The equality results from replacing log(n)-i by i. All that does is doing the sum in the opposite direction.
     
  14. Dec 23, 2015 #13
    Thanks Everybody I get it :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Approximating logarithmic series
  1. On logarithms (Replies: 7)

Loading...