# 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

Staff Emeritus
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

Staff Emeritus
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 :)