Query with regard to Algorithm Analysis

Question

So I came across this question in a problem set and the answer to the same is as follows:

I understand the outer for loop would basely run in linear time. The inner for loop, since they are multiples of an increasing input, I intuitively understand that the inner loop would run in logarithmic time and hence would run m times because of the outer loop. However, I don't seem to understand the mathematical proof for the same. As to why the ci[m/i] was used and the 1+ 1/2+1/4... segment of the solution. Could someone give me a better explanation for the same.

Answer 1

The second loop condition is equivalent to

for(pos = i;pos<=m;pos += i)

Here you can check that this loop will do $\lfloor{\cfrac mi}\rfloor$ operations each iteration of outer loop.

Now for the second part:

The sum $1 + \cfrac12 + \cfrac 13 + ......$

The sum is the area of squares (in the diagram) < Area under curve

$\int_0^m \cfrac 1x \,dx = ln(m)$

Which implies,

$\sum\limits_{i=1}^m \lfloor{\cfrac mi}\rfloor< ln(m)$

Hence, the time complexity $O(mlog(m)).$

Answer 2

I would've done something like this : for each round $i$ you execute $\left\lfloor \frac{m}{i} \right\rfloor$ instructions. For given $m$ you then have

$$ T(m) =\sum_{i=1}^m \left\lfloor \frac{m}{i} \right\rfloor \leq \sum_{i=1}^m \frac{m}{i} = m \sum_{i=1}^m \frac{1}{i} \leq m \log m \Rightarrow T(m) = O(m \log m). $$