1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ May 16 '20 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.