Calculated O(N/k) from k=1 to k=N

What do you want to do

I would like to calculate the calculation amount when calculating O(N/k) from k=1 to k=N.
(O is the order notation.)

That's why I'm trying to ask for it as follows, but I'm in trouble because I don't understand it

It seems that the following equation will be established if we ask for a rough order to calculate the calculated amount.
$__{k=1-N}(N/k)=NlogN$

How do I calculate this?

If you go a little further,
$__{k=1- }}(1/k)= 1$
and equality could be obtained from the infinite series sum.
$__{k=1-N}(1/k)=logN$
That means I don't know how to calculate.

I look forward to your kind cooperation.

c algorithm mathematics

2022-09-30 17:55

1 Answers

The series (partial sum of ) presented by the questioner has a name and is called a harmonic series (partial sum of ).
In general, I understand that the order is logN because the integral [[k=1,N+1]1/kdk=log(N+1) llogN and the partial sum of the series can be approximated as this integral.

For more detailed calculations, please refer to the following.

https://ja.wikipedia.org/wiki/%E8%AA%BF%E5%92%8C%E7%B4%9A%E6%95%B0#%E7%A9%8D%E5%88%86%E5%88%A4%E5%AE%9A%E6%B3%95

https://ameblo.jp/mossalmon/entry-12320091570.html

2022-09-30 17:55

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656