# Approximating logarithmic series

Tags:
1. Dec 23, 2015

### 22990atinesh

Can anybody tell me how this is possible

2. Dec 23, 2015

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

3. Dec 23, 2015

### 22990atinesh

http://sarielhp.org/teach/2003/b_273/notes/12_recc.pdf

4. Dec 23, 2015

### 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 ah, sorry: I see: L is the number of terms in $T(n)$.

5. Dec 23, 2015

### 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?

6. Dec 23, 2015

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

7. Dec 23, 2015

### 22990atinesh

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

8. Dec 23, 2015

### 22990atinesh

logarithm is base 2

9. Dec 23, 2015

### micromass

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

10. Dec 23, 2015

### 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 ?)

 ah, $\mu m$ was faster.

Last edited: Dec 23, 2015
11. Dec 23, 2015

### Samy_A

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.

12. Dec 23, 2015

### mathman

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.

13. Dec 23, 2015

### 22990atinesh

Thanks Everybody I get it :)