Big-O proof involving a sum of logs

Question

Prove that

I put the series into the summation, but I have no idea how to tackle this problem. Any help is appreciated

Answer 1

There are two useful mathematical facts that can help out here. First, note that ⌈x⌉ ≤ x + 1 for any x. Therefore,

sum from i = 1 to n (⌈log (n/i)⌉) ≤ (sum from i = 1 to n log (n / i)) + n

Therefore, if we can show that the second summation is O(n), we're done.

Using properties of logs, we can rewrite

log(n/1) + log(n/2) + ... + log(n/n)

= log(nⁿ / n!)

Let's see if we can simplify this. Using properties of logarithms, we get that

log(nⁿ / n!) = log(nⁿ) - log(n!)

= n log n - log (n!)

Now, we can use Stirling's approximation, which says that

log (n!) = n log n - n + O(log n)

Therefore:

n log n - log (n!)

= n log n - n log n + n - O(log n)

= O(n)

So the summation is O(n), as required.

Hope this helps!