Approximating logarithmic series

[22990atinesh]

Can anybody tell me how this is possible

 

[BvU]

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.

 

[22990atinesh]

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.

Please check this link
http://sarielhp.org/teach/2003/b_273/notes/12_recc.pdf

 

[BvU]

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)$.

 

[HallsofIvy]

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 $\frac{2}{log(2)- 0}= \frac{2}{1}$ which clearly is not true unless the logarithm is to be "base 2". Is that the case?

 

[Samy_A]

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.

 

[22990atinesh]

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.

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

 

[22990atinesh]

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 $\frac{2}{log(2)- 0}= \frac{2}{1}$ which clearly is not true unless the logarithm is to be "base 2". Is that the case?

logarithm is base 2

 

[micromass]

Can anybody tell me how this is possible
View attachment 93593

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$.

 

[BvU]

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.

 

[Samy_A]

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

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.

 

[mathman]

Can anybody tell me how this is possible
View attachment 93593

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.

 

[22990atinesh]

Thanks Everybody I get it :)