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.

  • 2
    $\begingroup$ 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 $\endgroup$
    – Tryss
    Feb 24 '15 at 19:38
  • 1
    $\begingroup$ I would never use $\log$ for base $10$ logarithm. Are you sure it mean this in that document? $\endgroup$
    – quid
    Feb 24 '15 at 19:43
  • 1
    $\begingroup$ I'm sorry I forgot to clarify that it was the binary logarithm. $\endgroup$
    – SherMM
    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) $$


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.