# Harmonic summation

I am studying a few algorithms books at the moment, and I often see the harmonic summation come up. What I am confused about is, if the harmonic summation is:

$$\sum_{i=1}^{n}1/i \sim \ln n$$

Why then do certain complexity analyses involving the harmonic sum, like the following one for Quicksort (from Skiena - Algorithm Design Manual pg. 49):

$$S(n) = n\sum_{i=1}^{n}1/i$$

Reduce to $\theta(n\log_2 n)$ and not $\theta(n \ln n)$

I am guessing for algorithmic analysis, this difference is not important, or I am just missing something entirely.

• It doesn't change anything, but also notice that sometime, $\log$ is the natural logarithm and not the decimal one... I know, it can be confusing Feb 24 '15 at 19:38
• I would never use $\log$ for base $10$ logarithm. Are you sure it mean this in that document?
– quid
Feb 24 '15 at 19:43
• I'm sorry I forgot to clarify that it was the binary logarithm. Feb 24 '15 at 19:44

It follows from the definition of natural logarithm and big-Oh notation: $$\log_a n = \frac{\ln n }{\ln a} = O(\ln n)$$