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 ∼ 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.

roletatx

roletatx

Open question

2022-09-01

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:
i = 1 n 1 / i 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 i = 1 n 1 / i
Reduce to θ ( n log 2 n ) and not θ ( n ln n )
I am guessing for algorithmic analysis, this difference is not important, or I am just missing something entirely.

Answer & Explanation

micelarnyiz

micelarnyiz

Beginner2022-09-02Added 8 answers

It follows from the definition of natural logarithm and big-Oh notation:
log a n = ln n ln a = O ( ln n )

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school statistics

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?