for all .

Results 1 to 7 of 7

- January 30th 2010, 06:04 PM #1

- Joined
- Jan 2010
- Posts
- 1

## Sum of log(i) up to n = O(nlogn)

First, I apologize if this is in the wrong section.

How do I go about demonstrating that the sum of log(i) from i up to n [eg. log(1) + log(2)... + log(n)] = O(n*logn)? That's Big-Oh notation. Any help/tips would be appreciated as I can't think where to start.

- January 30th 2010, 07:04 PM #2

- July 27th 2010, 03:36 AM #3

- Joined
- Jul 2010
- Posts
- 3

- July 27th 2010, 03:52 AM #4

- July 27th 2010, 05:52 AM #5

- Joined
- Jul 2010
- Posts
- 3

## Question

Thank you for your reply.

But it seems that I misunderstood. Are you able to conclude direcly from Black's proposition ?

Can you pass the equivalence to x-> infinity ? I have not done math for a long time but I remember it is not always such a basic thing to do.

- July 27th 2010, 06:43 AM #6
Yes, and easily at that. You need to make sure you understand what you need to show in order to prove that

Black has shown that

From this you get that

for , and with C=1, actually.

You really should look up the definition of Landau's Big-Oh notation, and preferably reproduce it without cheating on a white sheet of paper some time later. Definitions are very important in mathematics: without knowing them (or at the very least looking them up) you cannot hope to find the answer to an exercise like this.

- July 27th 2010, 07:55 AM #7

- Joined
- Jul 2010
- Posts
- 3