# What is the big-$O$ notation of a summation of a log?

For: $$\sum^{n+m}_{i=n} \log(i)$$ I'm wondering what the big O notation is and how to prove it... I believe that we can also write this as $$\log(n) + \log(n+1) + \log(n + 2) + \ldots + \log(n+m)$$

also $$\log(n+m)!/\log(n-1)!$$

Thanks

Recall that the sum of $$\log$$'s is equivalent to the $$\log$$ of products.

That is:

$$\log(xy) = \log x + \log y$$

Thus we can change your function:

\begin{align} \sum_{i=n}^{n+m} \log i &= \log \prod_{i = n}^{n + m} i\\ &= \log (n \cdot (n+1) \cdot (n+2) \cdot \ldots \cdot (m-1) \cdot m )\\ &= \log (m!\ /\ (n-1)! )\\ \end{align}

Then we can similarly use the division rule to get these back out:

$$\log (m!\ /\ (n-1)! ) = \log (m!) - \log((n-1)!)$$

Then using Stirling's Approximation we can immediately see:

$$\log (m!) - \log((n-1)!) = O(m \log m)$$

You might be able to do better though by taking more precise bounds to get:

\begin{align} \log (m!) - \log((n-1)!) &\leq em^{m + \frac{1}{2}}e^{-m} - \sqrt{2\pi}(n-1)^{n- \frac{1}{2}}e^{1-n}\\ &= \vdots \end{align}

O((m +1) log(n+m)). It’s obviously an upper bound. But also most values have a logarithm close to the maximum, so it’s also a good lower bound.

In your particularly simple case, the Stirling formula will give you a better result, but you asked for big-O only.

• Thanks so much -- so the big O is O(m+1)log(n+m)). ... sorry, but could you show why...I understand the log(n+m) part but not sure I understand where m+1 came from May 16 '20 at 4:10