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
    2017 Award

    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
    2017 Award

    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
    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
    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
    2017 Award

    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

    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 :)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook