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 follows from the definition of natural logarithm and big-Oh notation: $$ \log_a n = \frac{\ln n }{\ln a} = O(\ln n) $$